AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE
Chaim Linhart, Dan Halperin, Iddo Hanniel, Sariel Har-Peled · International Journal of Computational Geometry & Applications · 2003
Given a finite set ℒ of lines in the plane we wish to compute the zone of an additional curve γ in the arrangement [Formula: see text], namely the set of faces of the planar subdivision induced by the lines in ℒ that are crossed by γ, where γ 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). Our main algorithm is a novel approach based on the binary space partition technique. We implemented all four algorithms. We present implementation details, comparison of performance, and a discussion of the advantages and shortcomings of each of the proposed algorithms.