TY  - BOOK
AU  - Ghosh,Subir Kumar
TI  - Visibility algorithms in the plane
SN  - 9780511543340 (ebook)
AV  - TA1634 .G485 2007
U1  - 006.37 22
PY  - 2007///
CY  - Cambridge
PB  - Cambridge University Press
KW  - Computer vision
N1  - Title from publisher's bibliographic system (viewed on 05 Oct 2015); 1.1; Notion of Visibility; 1 --; 1.2; Polygon; 2 --; 1.3; Asymptotic Complexity; 5 --; 1.4; Triangulation; 6 --; 1.5; The Art Gallery Problem; 8 --; 1.6; Special Types of Visibility; 11 --; 2; Point Visibility; 13 --; 2.1; Problems and Results; 13 --; 2.2; Computing Visibility of a Point in Simple Polygons; 16 --; 2.2.1; Non-Winding Polygon: O(n) Algorithm; 16 --; 2.2.2; Removing Winding: O(n) Algorithm; 23 --; 2.3; Computing Visibility of a Point in Polygons with Holes; 31 --; 2.4; Recognizing Simple Polygons Visible from a Point; 38 --; 3; Weak Visibility and Shortest Paths; 46 --; 3.1; Problems and Results; 46 --; 3.2; Characterizing Weak Visibility; 51 --; 3.3; Computing Weak Visibility in Simple Polygons; 58 --; 3.3.1; Scanning the Boundary: O(n log n) Algorithm; 58 --; 3.3.2; Using Shortest Path Trees: O(n) Algorithm; 65 --; 3.4; Computing Weak Visibility in Polygons with Holes; 66 --; 3.5; Recognizing Weakly Internal Visible Polygons; 68 --; 3.5.1; Using Visibility Graph: O(E) Algorithm; 68 --; 3.5.2; Scanning the Boundary: O(n) Algorithm; 73 --; 3.6; Computing Shortest Path Trees; 82 --; 3.6.1; In Simple Polygons: O(n) Algorithm; 82 --; 3.6.2; In Weak Visibility Polygons: O(n) Algorithm; 87 --; 3.7; Recognizing Weakly External Visible Polygons; 95 --; 4; LR-Visibility and Shortest Paths; 105 --; 4.1; Problems and Results; 105 --; 4.2; Characterizing LR-Visibility; 108 --; 4.3; Computing LR-Visibility Polygons; 110 --; 4.4; Recognizing LR-Visibility Polygons; 113 --; 4.5; Walking in an LR-Visibility Polygon; 115 --; 4.6; Computing Shortest Path Trees using LR-Visibility; 124 --; 5; Visibility Graphs; 136 --; 5.1; Problems and Results; 136 --; 5.2; Computing Visibility Graphs of Simple Polygons; 138 --; 5.3; Computing Visibility Graphs of Polygons with Holes; 143 --; 5.3.1; Worst-Case: O(n[superscript 2]) Algorithm; 143 --; 5.3.2; Output-Sensitive: O(n log n + E) Algorithm; 146 --; 5.4; Computing Tangent Visibility Graphs; 161 --; 5.4.1; Convex Holes: O(n + h[superscript 2] log h) Algorithm; 161 --; 5.4.2; Non-Convex Holes: O(n + h[superscript 2] log h) Algorithm; 165 --; 6; Visibility Graph Theory; 171 --; 6.1; Problems and Results; 171 --; 6.2; Recognizing Visibility Graphs of Simple Polygons; 174 --; 6.2.1; Necessary Conditions; 174 --; 6.2.2; Testing Necessary Conditions: O(n[superscript 2]) Algorithm; 180 --; 6.3; Characterizing Visibility Graphs of Simple Polygons; 183 --; 6.4; Recognizing Special Classes of Visibility Graphs; 187 --; 6.4.1; Spiral Polygons: O(n) Algorithm; 187 --; 6.4.2; Tower Polygons: O(n) Algorithm; 195 --; 6.5; Characterizing a Sub-Class of Segment Visibility Graphs; 201 --; 6.6; A Few Properties of Vertex-Edge Visibility Graphs; 205 --; 6.7; Computing Maximum Clique in a Visibility Graph; 208 --; 6.8; Computing Maximum Hidden Vertex Set in a Visibility Graph; 214 --; 7; Visibility and Link Paths; 218 --; 7.1; Problems and Results; 218 --; 7.2; Computing Minimum Link Paths in Simple Polygons; 221 --; 7.2.1; Using Weak Visibility: O(n) Algorithm; 221 --; 7.2.2; Using Complete Visibility: O(n) Algorithm; 224 --; 7.3; Computing Minimum Link Paths in Polygons with Holes; 231 --; 7.4; Computing Link Center and Radius of Simple Polygons; 238 --; 7.5; Computing Minimum Nested Polygons; 242 --; 7.5.1; Between Convex Polygons: O(n log k) Algorithm; 242 --; 7.5.2; Between Non-Convex Polygons: O(n) Algorithm; 248 --; 8; Visibility and Path Queries; 255 --; 8.1; Problems and Results; 255 --; 8.2; Ray-Shooting Queries in Simple Polygons; 259 --; 8.3; Visibility Polygon Queries for Points in Polygons; 267 --; 8.3.1; Without Holes: O(log n + k) Query Algorithm; 267 --; 8.3.2; With Holes: O(n) Query Algorithm; 272 --; 8.4; Path Queries Between Points in Simple Polygons; 278 --; 8.4.1; Shortest Paths: O(log n + k) Query Algorithm; 278 --; 8.4.2; Link Paths: O(log n + k) Query Algorithm; 289
N2  - A human observer can effortlessly identify visible portions of geometric objects present in the environment. However, computations of visible portions of objects from a viewpoint involving thousands of objects is a time consuming task even for high speed computers. To solve such visibility problems, efficient algorithms have been designed. This book presents some of these visibility algorithms in two dimensions. Specifically, basic algorithms for point visibility, weak visibility, shortest paths, visibility graphs, link paths and visibility queries are all discussed. Several geometric properties are also established through lemmas and theorems. With over 300 figures and hundreds of exercises, this book is ideal for graduate students and researchers in the field of computational geometry.  It will also be useful as a reference for researchers working in algorithms, robotics, computer graphics and geometric graph theory, and some algorithms from the book can be used in a first course in computational geometry
UR  - https://doi.org/10.1017/CBO9780511543340
ER  -