Skip to main content
Journal cover image

A new approach to the dynamic maintenance of maximal points in a plane

Publication ,  Journal Article
Frederickson, GN; Rodger, S
Published in: Discrete & Computational Geometry
December 1, 1990

A point pi=(xi, yi) in the x-y plane is maximal if there is no point pj=(xj, yj) such that xj>xi and yj>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 that m maximal points are accessible in O(m) time. Our data structure dynamically maintains the set of points so that insertions take O(log n) time, a speedup of O(log n) over previous results, and deletions take O((log n)2) time. © 1990 Springer-Verlag New York Inc.

Duke Scholars

Published In

Discrete & Computational Geometry

DOI

EISSN

1432-0444

ISSN

0179-5376

Publication Date

December 1, 1990

Volume

5

Issue

1

Start / End Page

365 / 374

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Frederickson, G. N., & Rodger, S. (1990). A new approach to the dynamic maintenance of maximal points in a plane. Discrete & Computational Geometry, 5(1), 365–374. https://doi.org/10.1007/BF02187797
Frederickson, G. N., and S. Rodger. “A new approach to the dynamic maintenance of maximal points in a plane.” Discrete & Computational Geometry 5, no. 1 (December 1, 1990): 365–74. https://doi.org/10.1007/BF02187797.
Frederickson GN, Rodger S. A new approach to the dynamic maintenance of maximal points in a plane. Discrete & Computational Geometry. 1990 Dec 1;5(1):365–74.
Frederickson, G. N., and S. Rodger. “A new approach to the dynamic maintenance of maximal points in a plane.” Discrete & Computational Geometry, vol. 5, no. 1, Dec. 1990, pp. 365–74. Scopus, doi:10.1007/BF02187797.
Frederickson GN, Rodger S. A new approach to the dynamic maintenance of maximal points in a plane. Discrete & Computational Geometry. 1990 Dec 1;5(1):365–374.
Journal cover image

Published In

Discrete & Computational Geometry

DOI

EISSN

1432-0444

ISSN

0179-5376

Publication Date

December 1, 1990

Volume

5

Issue

1

Start / End Page

365 / 374

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0101 Pure Mathematics