Abstract
Let E be a set of n objects in fixed dimension d. We assume that each element of E has diameter smaller than D and has volume larger than V. We give a new divide and conquer algorithm that reports all the intersecting pairs in O(n log n + (Dd/V)(n + k)) time and using O(n) space, where k is the number of intersecting pairs. It makes use of simple data structures and primitive operations, which explains why it performs very well in practice. Its restriction to unit balls in low dimensions is optimal in terms of time complexity, space complexity and algebraic degree.
Original language | English (US) |
---|---|
Pages (from-to) | 87-92 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 85 |
Issue number | 2 |
DOIs | |
State | Published - Jan 31 2003 |
Externally published | Yes |
Keywords
- Algorithms
- Computational geometry
- Divide and conquer
- Geometric intersection problems
- Robustness
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications