Algorithms for Optimally Computing in-line Visibility and Their Applications.

Published in Volume XVI, 2006, pages 39-50

Authors: Mirel Coşulschi and Mihaela Sterpu

Abstract

In this paper, we approach a comparative study of two algorithms for calculating vertical segments visibility in certain situations. The first algorithm, Visibility, can be easily classified as a brute-force one, while the second algorithm is more elaborate, involving a better understanding of the problem and its peculiarity. A refinement of the second algorithm using the convex hull of a monotone polygon is derived. A thorough study of complexity of these algorithms is performed. An application of the visibility reporting algorithm to the efficient placement of some facilities in a practical problem is also given.

Bibtex

@article{sacscuza:coşulschi2006afocivata,
  title={Algorithms for Optimally Computing in-line Visibility and Their Applications.},
  author={Mirel Coşulschi and Mihaela Sterpu},
  journal={Scientific Annals of Computer Science},
  volume={16},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2006},
  pages={39--50},
  publisher={``A.I. Cuza'' University Press}
}