Implicitly representing arrangements of lines or segments (Q1263966)

Line arrangements, i.e. partitions of the plane by lines find numerous applications in computational geometry. However their full representation of size \(O(n^ 2)\) is sometimes excessive. The paper deals with the basic problem of face queries: given a query point p one has to retrieve the face containing p. Via geometric duality the latter problem is transformed into one of its own interest: given a planar pointset for any query line find convex hulls of points on both sides of it quickly. The paper presents algorithms with subquadratic space and preprocessing and sublinear face query time for arrangements of lines and line segments. A tradeoff for space vs. query time is also shown possible via random sampling method. Some other related problems are also considered.