Search
Close this search box.

On-line Zone Construction in Arrangements

Abstract

On-line Zone Construction in Arrangements
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.

Links

  • Chaim Linhart, Dan Halperin, S. Har-Peled, and Iddo Hanniel
    On-Line Zone Construction in Arrangements of Lines in the Plane
    International Journal of Computational Geometry and Applications, 13(6): 463–485, 2003 [link][bibtex]
  • Yuval Aharoni, Dan Halperin, Iddo Hanniel, Sariel Har-Peled, and Chaim Linhart
    On-Line Zone Construction in Arrangements of Lines in the Plane
    In Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE), Volume 1668 of LNCS, pages 139–153, Springer, London, 1999, [link][bibtex]
  • Sariel Har-Peled
    Taking a Walk in a Planar Arrangement
    SIAM Journal on Computing, 30(4): 1341–1367, 2000 [link][bibtex]

Contacts

Chaim Linhart 
@article{lhhh-esolm-03, 
  author = {C. Linhart, Dan Halperin,Iddo Hanniel and Sariel Har-Peled}, 
  title = {An experimental study of on-line methods for zone construction in arrangements of lines in the plane}, 
  journal = {International Journal of Computational Geometry and Applications}, 
  volume = {13}, 
  year = {2003}, 
  pages = {463--485}
}

@inproceedings{ahhhl-ozca-99,
  author = {Yuval Aharoni and Dan Halperin and Iddo Hanniel and Sariel Har-Peled and Chaim Linhart},
  title = {On-Line Zone Construction in Arrangements of Lines in the Plane},
  booktitle = {Proceedings of the 3rd Workshop on Algorithm Engineering (WAE)}, 
  year = {1999},
  pages = {139--153},
  publisher = {Springer-Verlag},
  volume = {1668},
  series = {Lecture Notes in Computer Science ({LNCS})},
  doi = {10.1007/3-540-48318-7_13}
}

@article{h-twpa-00,
  author = {Sariel Har-Peled},
  title = {Taking a Walk in a Planar Arrangement},
  journal = {{SIAM} Journal on Computing},
  volume = {30},
  number = {4},
  year = {2000},
  pages = {1341--1367},
  doi = {10.1137/S0097539799362627}
}

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content