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. In the first part of this thesis, we study the geometry of envelope polygons (simple polygons which are the envelope of some arrangement). We show that envelope polygons are L-convex and derive several geometric properties of envelopes. Also, given an envelope polygon P, we show how to sort by slope in linear time the lines colinear with the edges of P. Using this result, we give a linear time procedure to verify if a given polygon is an envelope polygon. In the second part of this thesis, 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$ sp2$) 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 have $ Omega$(n log n) complexity for arbitrary arrangements) can also 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 $ Omega$(n log n). Finally, we examine the existence of hamiltonian circuits through the intersection points of a non-trivial subclass of sail arrangements