Inducing polygons of line arrangements

E. Mumford, L. Scharf, M. Scherfenberg

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

1 Citation (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 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
PublisherLORIA
Pages107-110
Publication statusPublished - 2008

Fingerprint

Polygon
Arrangement
n-gon
Line
Path
Class

Cite this

Mumford, E., Scharf, L., & Scherfenberg, M. (2008). Inducing polygons of line arrangements. In S. Petitjean (Ed.), Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008) (pp. 107-110). Vandoeuvre-lès-Nancy: LORIA.
Mumford, E. ; Scharf, L. ; Scherfenberg, M. / Inducing polygons of line arrangements. Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008). editor / S. Petitjean. Vandoeuvre-lès-Nancy : LORIA, 2008. pp. 107-110
@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",

}

Mumford, E, Scharf, L & Scherfenberg, M 2008, Inducing polygons of line arrangements. in S Petitjean (ed.), Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008). LORIA, Vandoeuvre-lès-Nancy, pp. 107-110.

Inducing polygons of line arrangements. / Mumford, E.; Scharf, L.; Scherfenberg, M.

Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008). ed. / S. Petitjean. Vandoeuvre-lès-Nancy : LORIA, 2008. p. 107-110.

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

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 -

Mumford E, Scharf L, Scherfenberg M. Inducing polygons of line arrangements. In Petitjean S, editor, Abstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008). Vandoeuvre-lès-Nancy: LORIA. 2008. p. 107-110