Dynamic half-space reporting, geometric optimization, and minimum spanning trees

Conference Paper

The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Eppstein, D; Matousek, J

Published Date

  • January 1, 1992

Published In

Volume / Issue

  • 1992-October /

Start / End Page

  • 80 - 89

International Standard Serial Number (ISSN)

  • 0272-5428

International Standard Book Number 10 (ISBN-10)

  • 0818629002

Digital Object Identifier (DOI)

  • 10.1109/SFCS.1992.267816

Citation Source

  • Scopus