An experimental study of on-line methods for zone construction in arrangements of lines in the plane

摘要

Given a finite 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 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.