On Envelopes of Arrangements of Lines

✍ Scribed by D. Eu; E. Guévremont; G.T. Toussaint

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 436 KB
• Volume: 21
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0040

✦ Synopsis

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 Ž Ž 2 . . 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 ar-. Ž . rangements 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