As an informal motivation the problem, imagine a tower with polygonal footprint, that is located in a beautiful landscape, the "Belvedere Hull" is then related to the directions, in which one would have a view unobstructed by the tower (it is assumed that the tower has roof, so it is not possible to stand on top of it).

given a simple, planar polygon, calculate the boundary of the union of all half-lines that do not contain inner points of the polygon, i.e. the "Belvedere Hull".

This problem seems to be related to the visibility from a point inside the polygon, or to the art gallery problem, so I would like to know if this problem has already been considered or, how to tackle it.

Generalizations can easily be envisaged, by either going to higher-dimensional spaces and/or, by replacing the polygon by other, not necessarily connected point-sets.


Your concept is called a weakly externally visible polygon in the literature.

The above figure is from the chapter, "Visibility in the Plane" by Asano, Ghosh, Shermer, in The Handbook of Computational Geometry. Likely Ghosh's book is the best source:

Ghosh, Subir Kumar. Visibility algorithms in the plane. (Vol.2). Cambridge: Cambridge University Press, 2007.

The concept is studied extensively in the context of 3D graphics, e.g.,

Wang, Caoan, and Binhai Zhu. "Three dimensional weak visibility: Complexity and applications." Computing and Combinatorics. Springer Berlin Heidelberg, 1995. 51-60.

  • $\begingroup$ thanks for providing the name of my problem and for the pointers to the literature. $\endgroup$ – Manfred Weis Nov 21 '14 at 15:28
  • $\begingroup$ @ManfredWeis: I am aware that I didn't directly answer your question about the weakly visible hull. It may be in those references, either explicitly or implicitly. $\endgroup$ – Joseph O'Rourke Nov 21 '14 at 22:51
  • $\begingroup$ that is often the hard part, namely to get to know the name of a problem as the magic word that grants access to further information; so your answer is perfectly ok for me. $\endgroup$ – Manfred Weis Nov 22 '14 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.