Inducing polygons of line arrangements

E. Mumford; L. Scharf; M. Scherfenberg

Inducing polygons of line arrangements

E. Mumford, L. Scharf, M. Scherfenberg

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

2 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008)
Editors	S. Petitjean
Place of Publication	Vandoeuvre-lès-Nancy
Publisher	LORIA
Pages	107-110
Publication status	Published - 2008

Cite this

@inproceedings{4b3c05225baf4408b6e3d9ba5625257a,

title = "Inducing polygons of line arrangements",

abstract = "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.",

author = "E. Mumford and L. Scharf and M. Scherfenberg",

year = "2008",

language = "English",

pages = "107--110",

editor = "S. Petitjean",

booktitle = "Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008)",

publisher = "LORIA",

}

TY - GEN

T1 - Inducing polygons of line arrangements

AU - Mumford, E.

AU - Scharf, L.

AU - Scherfenberg, M.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 107

EP - 110

BT - Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008)

A2 - Petitjean, S.

PB - LORIA

CY - Vandoeuvre-lès-Nancy

ER -

Inducing polygons of line arrangements

Abstract

Fingerprint

Cite this