Chapter 15 - Arrangements of line segments in the plane

Summary

In an arrangement of n lines in the plane, all the cells are convex and thus have complexity O(n). Moreover, given a point A, the cell in the arrangement that contains A can be computed in time Θ(n log n): indeed, the problem reduces to computing the intersection of n half-planes bounded by the lines and containing A (see theorem 7.1.10).

In this chapter, we study arrangements of line segments in the plane. Consider a set S of n line segments in the plane. The arrangement of S includes cells, edges, and vertices of the planar subdivision of the plane induced by S, and their incidence relationships.

Computing the arrangement of S can be achieved in time O(n log n + k) where k is the number of intersection points (see sections 3.3 and 5.3.2, and theorem 5.2.5). All the pairs of segments may intersect, so in the worst case we have k = Ω(n²).

For a few applications, only a cell in this arrangement is needed. This is notably the case in robotics, for a polygonal robot moving amidst polygonal obstacles by translation (see exercise 15.6). The reachable positions are characterized by lying in a single cell of the arrangement of those line segments that correspond to the set of positions of the robot when a vertex of the robot slides along the edge of an obstacle, or when the edge of a robot maintains contact with an obstacle at a point.