Dynamic polar diagram

The polar diagram [C.I. Grima, A. Márquez, L. Ortega, A new 2D tessellation for angle problems: The polar diagram, Computational Geometry 34 (2006) 58–74] of a set of points on the plane and the contracted dual of polar diagram (CDPD) [B. Sadeghi Bigham, A. Mohades, The dual of polar diagrams and its extraction, in: International Conference of Computational Methods in Sciences and Engineering ICCMSE, vol. 7, Greece, 2006, pp. 451–454] have been introduced recently. In this paper, we introduce the Dynamic Polar Diagram and present an algorithm to find it using CDPD and a hash structure for point location problem. In the dynamic polar diagram, the points can be added to or removed from the point set. For this problem, a brute-force method runs in O(nlogn) time and also there is a sketch of an algorithm in [C.I. Grima, A. Márquez, L. Ortega, A new 2D tessellation for angle problems: The polar diagram, Computational Geometry 34 (2006) 58–74] that takes O(n) time in all cases (best, average and worst). In our approach, we first determine an area out of which the polar diagram does not change due to insertion or deletion of a site. Then we present a new algorithm to solve the problem in O(kp) time where kp is the number of the sites whose polar regions are affected by the new addition or deletion of p.