Reporting intersections among thick objects

Antoine Vigneron*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)87-92
Number of pages6
JournalInformation Processing Letters
Volume85
Issue number2
DOIs
StatePublished - Jan 31 2003
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Reporting intersections among thick objects'. Together they form a unique fingerprint.

Cite this