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

Research output: Contribution to journalArticlepeer-review

Abstract

Given a finite set ℒ of lines in the plane we wish to compute the zone of an additional curve γ in the arrangement A(ℒ), 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.

Original languageEnglish (US)
Pages (from-to)463-485
Number of pages23
JournalInternational Journal of Computational Geometry and Applications
Volume13
Issue number6
DOIs
StatePublished - Dec 2003

Keywords

  • Arrangements of lines
  • Binary space partition
  • Convex hulls
  • Half-plane intersection
  • On-line algorithms
  • Zone

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'An experimental study of on-line methods for zone construction in arrangements of lines in the plane'. Together they form a unique fingerprint.

Cite this