Reporting and counting segment intersections

摘要

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 nlog 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.