Towards in-place geometric algorithms and data structures

Hervé Brönnimann, Timothy M. Chan, Eric Y. Chen

Research output: Contribution to conferencePaperpeer-review

Abstract

For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

Original languageEnglish (US)
Pages239-246
Number of pages8
DOIs
StatePublished - Jan 1 2004
Externally publishedYes
EventProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States
Duration: Jun 9 2004Jun 11 2004

Other

OtherProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
CountryUnited States
CityBrooklyn, NY
Period6/9/046/11/04

Keywords

  • Convex hulls
  • In-place algorithms
  • Range searching
  • Voronoi diagrams

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Towards in-place geometric algorithms and data structures'. Together they form a unique fingerprint.

Cite this