INDUCING POLYGONS OF LINE ARRANGEMENTS
Ludmila Scharf, Marc Scherfenberg · International Journal of Computational Geometry & Applications · 2011
We show that an arrangement [Formula: see text] 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 [Formula: see text] 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.