Publications [#237137] of Susan H. Rodger

Conference articles OFFICIALLY ACCEPTED

1. Frederickson, GN; Rodger, S, A new approach to the dynamic maintenance of maximal points in a plane, Discrete Computational Geometry, vol. 5 no. 1 (December, 1990), pp. 365-374, Springer Nature, ISSN 0179-5376 [doi]
   (last updated on 2026/01/19)

   Abstract:
   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)²) time. © 1990 Springer-Verlag New York Inc.