On-line zone construction in arrangements of lines in the plane

Yuval Aharoni; Dan Halperin; Iddo Hanniel; Sariel Har-Peled; Chaim Linhart

doi:10.1007/3-540-48318-7_13

On-line zone construction in arrangements of lines in the plane

Yuval Aharoni, Dan Halperin, Iddo Hanniel, Sariel Har-Peled, Chaim Linhart

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

Abstract

Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by, where is not given in advance but rather provided online portion by portion. This problem is motivated by the computation of the area bisectors of a polygonal set in the plane. We present four algorithms which solve this problem efficiently and exactly (giving precise results even on degenerate input). We implemented the four algorithms. We present implementation details, comparison of performance, and a iscussion of the advantages and shortcomings of each of the proposed algorithms.

Original language	English (US)
Title of host publication	Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings
Editors	Jeffrey S. Vitter, Christos D. Zaroliagis
Publisher	Springer
Number of pages	1
ISBN (Print)	3540664270, 9783540664277
DOIs	https://doi.org/10.1007/3-540-48318-7_13
State	Published - 1999
Externally published	Yes
Event	3rd International Workshop on Algorithm Engineering, WAE 1999 - London, United Kingdom Duration: Jul 19 1999 → Jul 21 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1668
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd International Workshop on Algorithm Engineering, WAE 1999
Country/Territory	United Kingdom
City	London
Period	7/19/99 → 7/21/99

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/3-540-48318-7_13

Library availability

Discover UIUC Full Text

Cite this

Aharoni, Y., Halperin, D., Hanniel, I., Har-Peled, S., & Linhart, C. (1999). On-line zone construction in arrangements of lines in the plane. In J. S. Vitter, & C. D. Zaroliagis (Eds.), Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1668). Springer. https://doi.org/10.1007/3-540-48318-7_13

On-line zone construction in arrangements of lines in the plane. / Aharoni, Yuval; Halperin, Dan; Hanniel, Iddo et al.
Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. ed. / Jeffrey S. Vitter; Christos D. Zaroliagis. Springer, 1999. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1668).

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

Aharoni, Y, Halperin, D, Hanniel, I, Har-Peled, S & Linhart, C 1999, On-line zone construction in arrangements of lines in the plane. in JS Vitter & CD Zaroliagis (eds), Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1668, Springer, 3rd International Workshop on Algorithm Engineering, WAE 1999, London, United Kingdom, 7/19/99. https://doi.org/10.1007/3-540-48318-7_13

Aharoni Y, Halperin D, Hanniel I, Har-Peled S, Linhart C. On-line zone construction in arrangements of lines in the plane. In Vitter JS, Zaroliagis CD, editors, Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. Springer. 1999. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-48318-7_13

Aharoni, Yuval ; Halperin, Dan ; Hanniel, Iddo et al. / On-line zone construction in arrangements of lines in the plane. Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings. editor / Jeffrey S. Vitter ; Christos D. Zaroliagis. Springer, 1999. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b8969c41c7834248bb02e9adbf807243,

title = "On-line zone construction in arrangements of lines in the plane",

abstract = "Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by, where is not given in advance but rather provided online portion by portion. This problem is motivated by the computation of the area bisectors of a polygonal set in the plane. We present four algorithms which solve this problem efficiently and exactly (giving precise results even on degenerate input). We implemented the four algorithms. We present implementation details, comparison of performance, and a iscussion of the advantages and shortcomings of each of the proposed algorithms.",

author = "Yuval Aharoni and Dan Halperin and Iddo Hanniel and Sariel Har-Peled and Chaim Linhart",

year = "1999",

doi = "10.1007/3-540-48318-7_13",

language = "English (US)",

isbn = "3540664270",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

editor = "Vitter, {Jeffrey S.} and Zaroliagis, {Christos D.}",

booktitle = "Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings",

address = "Germany",

note = "3rd International Workshop on Algorithm Engineering, WAE 1999 ; Conference date: 19-07-1999 Through 21-07-1999",

}

TY - GEN

T1 - On-line zone construction in arrangements of lines in the plane

AU - Aharoni, Yuval

AU - Halperin, Dan

AU - Hanniel, Iddo

AU - Har-Peled, Sariel

AU - Linhart, Chaim

PY - 1999

Y1 - 1999

N2 - Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by, where is not given in advance but rather provided online portion by portion. This problem is motivated by the computation of the area bisectors of a polygonal set in the plane. We present four algorithms which solve this problem efficiently and exactly (giving precise results even on degenerate input). We implemented the four algorithms. We present implementation details, comparison of performance, and a iscussion of the advantages and shortcomings of each of the proposed algorithms.

AB - Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by, where is not given in advance but rather provided online portion by portion. This problem is motivated by the computation of the area bisectors of a polygonal set in the plane. We present four algorithms which solve this problem efficiently and exactly (giving precise results even on degenerate input). We implemented the four algorithms. We present implementation details, comparison of performance, and a iscussion of the advantages and shortcomings of each of the proposed algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84957045760&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957045760&partnerID=8YFLogxK

U2 - 10.1007/3-540-48318-7_13

DO - 10.1007/3-540-48318-7_13

M3 - Conference contribution

AN - SCOPUS:84957045760

SN - 3540664270

SN - 9783540664277

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

BT - Algorithm Engineering - 3rd International Workshop, WAE 1999, Proceedings

A2 - Vitter, Jeffrey S.

A2 - Zaroliagis, Christos D.

PB - Springer

T2 - 3rd International Workshop on Algorithm Engineering, WAE 1999

Y2 - 19 July 1999 through 21 July 1999

ER -

On-line zone construction in arrangements of lines in the plane

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this