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( log² 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(n^1.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.