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

Journal Article (Journal Article)

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.

Full Text

Duke Authors

Cited Authors

  • Frederickson, GN; Rodger, S

Published Date

  • December 1, 1990

Published In

Volume / Issue

  • 5 / 1

Start / End Page

  • 365 - 374

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/BF02187797

Citation Source

  • Scopus