Paper Info
Title
Efficient Algorithms for Computing a Complete Visibility Region in Three-Dimensional Space
Abstract
.    Given a set P of polygons in three-dimensional space, two points p and q are said to be visible from each other with respect to P if the line segment joining them does not intersect any polygon in P . A point p is said to be completely visible from an area source S if p is visible from every point in S . The completely visible region CV(S, P) from S with respect to P is defined as the set of all points in three-dimensional space that are completely visible from S . We present two algorithms for computing CV(S, P) for P with a total of n vertices and a convex polygonal source S with m vertices. Our first result is a divide-and-conquer algorithm which runs in O(m 2 n 2 α(mn)) time and space, where α(mn) is the inverse of Ackermann's function. We next give an incremental algorithm for computing CV(S,P) in O(m 2 n+mn 2 α(n)) time and O(mn+n 2 ) space. We also prove that CV(S,P) consists of Θ(mn+n 2 ) surface elements such as vertices, edges, and faces.
Year
DOI
Venue
1998
10.1007/PL00009193
Algorithmica
Keywords
Field
DocType
Key words. Computational geometry,Complete visibility,Penumbra.
Discrete mathematics,Three-dimensional space,Line segment,Combinatorics,Polygon,Computational geometry,Image processing,Algorithm,Visibility polygon,Time complexity,Mathematics,The Intersect
Journal
Volume
Issue
ISSN
20
2
0178-4617
Citations 
PageRank 
References 
3
0.40
16
Authors
4
Name
Order
Citations
PageRank
Dae Seoung Kim1101.34
Kwan-Hee Yoo22812.18
Kyung-Yong Chwa391997.10
Sung Yong Shin41904168.33