1. INDUCING POLYGONS OF LINE ARRANGEMENTS.
- Author
-
SCHARF, LUDMILA, SCHERFENBERG, MARC, Hong, Seok-Hee, and Nagamochi, Niroshi
- Subjects
- *
COMBINATORICS , *POLYGONS , *PLANE geometry , *ALGORITHMS , *INTERSECTION theory , *MATHEMATICAL analysis - Abstract
We show that an arrangement $\mathcal{A}$ of n lines in general position in the plane has an inducing polygon of size O(n). Additionally, we present a simple algorithm for finding an inducing n-path for $\mathcal{A}$ in O(n log n) time and an algorithm that constructs an inducing n-gon for a special class of line arrangements within the same time bound. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF