Abstract
Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, planes, and polyhedra in three dimensions.
Original language | English (US) |
---|---|
Pages (from-to) | 348-361 |
Number of pages | 14 |
Journal | Journal of Algorithms |
Volume | 8 |
Issue number | 3 |
DOIs | |
State | Published - Sep 1987 |
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics