VC-dimension of exterior visibility

Volkan Isler, Sampath Kannan, Kostas Daniilidis, Pavel Valtr

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


In this paper, we study the Vapnik-Chervonenkis (VC)-dimension of set systems arising in 2D polygonal and 3D polyhedral configurations where a subset consists of all points visible from one camera. In the past, it has been shown that the VC-dimension of planar visibility systems is bounded by 23 if the cameras are allowed to be anywhere inside a polygon without holes [1]. Here, we consider the case of exterior visibility, where the cameras lie on a constrained area outside the polygon and have to observe the entire boundary. We present results for the cases of cameras lying on a circle containing a polygon (VC-dimension=2) or lying outside the convex hull of a polygon (VC-dimension=5). The main result of this paper concerns the 3D case: We prove that the VC-dimension is unbounded if the cameras lie on a sphere containing the polyhedron, hence the term exterior visibility.

Original languageEnglish (US)
Pages (from-to)667-671
Number of pages5
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number5
StatePublished - May 2004

Bibliographical note

Funding Information:
The authors highly appreciate the comments by the anonymous reviewers, which substantially improved the readability of the paper. The first three authors are grateful for support through the following grants: US National Science Foundation NSF-IIS-0083209, NSF-IIS-0121293, NSF-CCR-98-20885, NSF-CCR-01-05337, MURI DAAH-19-02-1-03-83, and a Penn Research Foundation grant. Research by P. Valtr was supported by project LN00A056 of The Ministry of Education of the Czech Republic.


  • Sampling
  • Sensor placement
  • VC-dimension
  • Visibility


Dive into the research topics of 'VC-dimension of exterior visibility'. Together they form a unique fingerprint.

Cite this