Maintaining the extent of a moving point set

Published

Conference Paper

© Springer-Verlag Berlin Heidelberg 1997. Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of the points. When the points in S move with pseudo-algebraic motions, these structures process O(n2+ε) events. We also give constructions showing that Ω(n2) combinatorial changes are possible in these extent functions even when the points move on straight lines with constant velocities. We give a similar construction and upper bound for the convex hull, improving known results.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Guibas, LJ; Hershberger, J; Veach, E

Published Date

  • January 1, 1997

Published In

Volume / Issue

  • 1272 /

Start / End Page

  • 31 - 44

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540633073

International Standard Book Number 13 (ISBN-13)

  • 9783540633075

Digital Object Identifier (DOI)

  • 10.1007/3-540-63307-3_46

Citation Source

  • Scopus