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 W(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 O(n 2 ) vertices), we show how the prune-and-search techni..