Inducing polygons of line arrangements

E. Mumford, L. Scharf, M. Scherfenberg

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


We show that an arrangement 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 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.
Original languageEnglish
Title of host publicationAbstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008)
EditorsS. Petitjean
Place of PublicationVandoeuvre-lès-Nancy
Publication statusPublished - 2008


Dive into the research topics of 'Inducing polygons of line arrangements'. Together they form a unique fingerprint.

Cite this