On Envelopes of Arrangements of Lines

The envelope of an arrangement of lines is the polygon consisting of the finite length segments that bound the infinite faces of the arrangement. We study the geometry of envelope polygons (simple polygons that are the envelope of some arrangement). We show that envelope polygons are L-convex and derive several geometric properties of envelopes. Given an envelope polygon P of n vertices, we show how to sort its edges by slope in O(n) time (for unrestricted simple polygons this problem has complexity Ω(n log n)). Using this result, we give a linear time procedure to verify if a given polygon is an envelope polygon. We introduce a hierarchy of classes of arrangements of lines based on the number of convex vertices of their envelopes. In particular, we look at a class called sail arrangements, which we prove has properties that enable us to solve a number of problems optimally. Given a sail arrangement consisting of n lines (and Θ(n²) vertices), we show how the prune-and-search technique can be used to determine all the convex vertices of its envelope in O(n) time. This implies that the intersection point with minimum or maximum x-coordinate, the diameter, and the convex hull of sail arrangements (problems that also have Ω(n log n) complexity for arbitrary arrangements) can be found in O(n) time. We show, in spite of this, that the problem of constructing the full envelope of a sail arrangement still has a lower bound of Ω(n log n). We also examine the existence of hamiltonian circuits through the intersection points of a nontrivial subclass of sail arrangements. Finally, we establish an Ω(n log n) time lower bound for the problem of constructing a hamiltonian circuit through the vertices of an arrangement of n lines, where only the vertices where a turn is made need be output.