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 language | English (US) |
|---|---|
| Pages | 239-246 |
| Number of pages | 8 |
| DOIs | |
| State | Published - 2004 |
| Externally published | Yes |
| Event | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004 |
Other
| Other | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) |
|---|---|
| Country/Territory | United States |
| City | Brooklyn, NY |
| Period | 6/9/04 → 6/11/04 |
Keywords
- Convex hulls
- In-place algorithms
- Range searching
- Voronoi diagrams
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics