Abstract
A pointp i=(x i, yi) in thex–y plane ismaximal if there is no pointp j=(x j, yj) such thatx j>xi andy j>yi. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)2) time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
H. T. Kung, F. Luccio, and F. P. Preparata, On finding the maxima of a set of vectors,J. Assoc. Comput. Mach. 22, 4 (1975), 469–476.
M. H. Overmars and J. L. van Leeuwen, Maintenance of configurations in the plane,J. Comp. System Sci. 23 (1981), 166–204.
R. E. Tarjan, Updating a balanced search tree inO(1) rotations,Inform. Process. Lett. 16 (1983), 253–257.
D. E. Willard and G. S. Lueker, Adding range restriction capability to dynamic data structures,J. Assoc. Comput. Mach. 32, 3 (1985), 597–617.
Author information
Authors and Affiliations
Additional information
The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.
Rights and permissions
About this article
Cite this article
Frederickson, G.N., Rodger, S. A new approach to the dynamic maintenance of maximal points in a plane. Discrete Comput Geom 5, 365–374 (1990). https://doi.org/10.1007/BF02187797
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187797