Two-dimensional visibility charts for continuous curves

Elber, G, Sayegh, R., Barequet, G. and Martin, Ralph Robert 2005. Two-dimensional visibility charts for continuous curves. Presented at: International Conference on Shape Modeling and Applications, Cambridge, MA, USA, 13-17 June 2005. Proceedings of the Shape Modeling and Applications, 2005 International Conference, 13-17 June 2005. IEEE, pp. 206-215. 10.1109/SMI.2005.48

Preview

PDF Download (292kB) | Preview

Abstract

This paper considers computation of visibility for two-dimensional shapes whose boundaries are C1 continuous curves. We assume we are given a one-parameter family of candidate viewpoints, which may be interior or exterior to the object, and at finite or infinite locations. We consider how to compute whether the whole boundary of the shape is visible from some finite set of viewpoints taken from this family, and if so, how to compute a minimal set of such viewpoints. The viewpoint families we handle include (i) the set of viewing directions from infinity, (ii) viewpoints on a circle located outside the object (for inspection from a turntable), and (iii) viewpoints located on the walls of the shape itself. We compute a structure called a visibility chart, which simultaneously encodes the visible part of the shape's boundary from every view in the family. Using such a visibility chart, finding a minimal set of viewpoints reduces to the set-covering problem over the reals. Practical algorithms are obtained by a discrete sampling of the visibility chart. For exterior visibility problems, a reasonable approach is to compute an almost-optimal solution (in terms of number of viewpoints), which can be done in almost-linear time. For interior visibility problems, or when a more correct solution is required, we solve the general set-covering problem, guaranteeing an optimal solution but taking exponential time.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software
Uncontrolled Keywords:	2D visibility charts; candidate viewpoint; continuous curve; discrete sampling; finite set; set-covering problem
Additional Information:	PDF uploaded in accordance with publisher's policy http://www.ieee.org/publications_standards/publications/rights/rights_policies.html [accessed 22/01/2015] ©2005 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Publisher:	IEEE
ISBN:	076952379X
Last Modified:	10 Nov 2023 16:22
URI:	https://orca.cardiff.ac.uk/id/eprint/31779

Citation Data

Cited 13 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item