On Envelopes of Arrangements of Lines

D. Eu, E. Guévremont, G. T. Toussaint

Research output: Contribution to journalArticle

Abstract

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 Θ(n2) 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.

Original languageEnglish (US)
Pages (from-to)111-148
Number of pages38
JournalJournal of Algorithms
Volume21
Issue number1
DOIs
StatePublished - Jul 1996

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On Envelopes of Arrangements of Lines'. Together they form a unique fingerprint.

  • Cite this