TY - GEN

T1 - Intersecting is easier than sorting

AU - Chaselle, Bernard

PY - 1984/12/1

Y1 - 1984/12/1

N2 - This paper settles a long-standing open question of computational geometry: Is it possible to compute all k intersections between n arbitrary line segments in time linear in k? We answer this question affirmatively by presenting the first algorithm with a running time of the form O(k+f(n)), where I is a sub quadratic function of n. The function f we achieve is actually quasi-linear in n, which makes our algorithm the most efficient to date for each value of k. To obtain this result we must turn away from traditional, sweep-line-based schemes. Instead, we introduce a new hierarchical strategy for dealing with segments without ever reducing the dimensionality of the problem. This framework is used to solve other related problems. In particular, we are able to present the first subquadratic algorithm for computing intersections (as opposed to reporting each of them explicitly}, and we give the first 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.

AB - This paper settles a long-standing open question of computational geometry: Is it possible to compute all k intersections between n arbitrary line segments in time linear in k? We answer this question affirmatively by presenting the first algorithm with a running time of the form O(k+f(n)), where I is a sub quadratic function of n. The function f we achieve is actually quasi-linear in n, which makes our algorithm the most efficient to date for each value of k. To obtain this result we must turn away from traditional, sweep-line-based schemes. Instead, we introduce a new hierarchical strategy for dealing with segments without ever reducing the dimensionality of the problem. This framework is used to solve other related problems. In particular, we are able to present the first subquadratic algorithm for computing intersections (as opposed to reporting each of them explicitly}, and we give the first 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.

UR - http://www.scopus.com/inward/record.url?scp=1542455832&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1542455832&partnerID=8YFLogxK

U2 - 10.1145/800057.808674

DO - 10.1145/800057.808674

M3 - Conference contribution

AN - SCOPUS:1542455832

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 125

EP - 134

BT - Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984

PB - Association for Computing Machinery

T2 - 16th Annual ACM Symposium on Theory of Computing, STOC 1984

Y2 - 30 April 1984 through 2 May 1984

ER -