Reporting and counting segment intersections

Research output: Contribution to journalArticle

43 Scopus citations

Abstract

This paper partly settles the following question: Is it possible to compute all k intersections between n arbitrary line segments in time linear in k? We describe an algorithm for this problem whose running time is O(n( log2 n log log n)+k). This is the first solution with a time bound linear in the size of the output. To obtain this result we turn away from traditional, sweep-line-based schemes. Instead, we introduce a new hierarchical strategy for dealing with segments without reducing the dimensionality of the problem. This framework is also used to answer related questions. New results include an O(n1.695) time algorithm for counting intersections (as opposed to reporting each of them explicitly) and an optimal algorithm for computing the intersections of a line arrangement with a query segment. Using duality arguments we also present an improved algorithm for a point enclosure problem.

Original languageEnglish (US)
Pages (from-to)156-182
Number of pages27
JournalJournal of Computer and System Sciences
Volume32
Issue number2
DOIs
StatePublished - Apr 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Reporting and counting segment intersections'. Together they form a unique fingerprint.

  • Cite this