On-line Zone Construction in Arrangements of Lines in the
Plane
Y. Aharoni, D. Halperin, I. Hanniel, S. Har-Peled, C. Linhart
Given a finite set L of lines in the plane we wish to compute
the zone of an additional curve c in the arrangement
\A(L), namely the set of faces of the planar subdivision
induced by the lines in L that are crossed by c, where
c is not given in advance but rather provided on-line
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 discussion of the advantages and shortcomings of
each of the proposed algorithms.
Postscript :
PDFProgram Source
@inproceedings{ahhhl-olzca-99,
author = {Y.~Aharoni and D.~Halperin and I.~Hanniel and
S.~Har-Peled and C.~Linhart},
title = {On-line Zone Construction in Arrangements of Lines in the
Plane},
booktitle = "Proc. Workshop on Algorithm Engineering",
nickname = "WAE '99",
year = 1999,
pages = {139--153}
}