Visibility algorithms in the plane /
Subir Kumar Ghosh.
- Cambridge : Cambridge University Press, 2007.
- 1 online resource (xiii, 318 pages) : digital, PDF file(s).
Title from publisher's bibliographic system (viewed on 05 Oct 2015).
Notion of Visibility Polygon Asymptotic Complexity Triangulation The Art Gallery Problem Special Types of Visibility Point Visibility Problems and Results Computing Visibility of a Point in Simple Polygons Non-Winding Polygon: O(n) Algorithm Removing Winding: O(n) Algorithm Computing Visibility of a Point in Polygons with Holes Recognizing Simple Polygons Visible from a Point Weak Visibility and Shortest Paths Problems and Results Characterizing Weak Visibility Computing Weak Visibility in Simple Polygons Scanning the Boundary: O(n log n) Algorithm Using Shortest Path Trees: O(n) Algorithm Computing Weak Visibility in Polygons with Holes Recognizing Weakly Internal Visible Polygons Using Visibility Graph: O(E) Algorithm Scanning the Boundary: O(n) Algorithm Computing Shortest Path Trees In Simple Polygons: O(n) Algorithm In Weak Visibility Polygons: O(n) Algorithm Recognizing Weakly External Visible Polygons LR-Visibility and Shortest Paths Problems and Results Characterizing LR-Visibility Computing LR-Visibility Polygons Recognizing LR-Visibility Polygons Walking in an LR-Visibility Polygon Computing Shortest Path Trees using LR-Visibility Visibility Graphs Problems and Results Computing Visibility Graphs of Simple Polygons Computing Visibility Graphs of Polygons with Holes Worst-Case: O(n[superscript 2]) Algorithm Output-Sensitive: O(n log n + E) Algorithm Computing Tangent Visibility Graphs Convex Holes: O(n + h[superscript 2] log h) Algorithm Non-Convex Holes: O(n + h[superscript 2] log h) Algorithm Visibility Graph Theory Problems and Results Recognizing Visibility Graphs of Simple Polygons Necessary Conditions Testing Necessary Conditions: O(n[superscript 2]) Algorithm Characterizing Visibility Graphs of Simple Polygons Recognizing Special Classes of Visibility Graphs Spiral Polygons: O(n) Algorithm Tower Polygons: O(n) Algorithm Characterizing a Sub-Class of Segment Visibility Graphs A Few Properties of Vertex-Edge Visibility Graphs Computing Maximum Clique in a Visibility Graph Computing Maximum Hidden Vertex Set in a Visibility Graph Visibility and Link Paths Problems and Results Computing Minimum Link Paths in Simple Polygons Using Weak Visibility: O(n) Algorithm Using Complete Visibility: O(n) Algorithm Computing Minimum Link Paths in Polygons with Holes Computing Link Center and Radius of Simple Polygons Computing Minimum Nested Polygons Between Convex Polygons: O(n log k) Algorithm Between Non-Convex Polygons: O(n) Algorithm Visibility and Path Queries Problems and Results Ray-Shooting Queries in Simple Polygons Visibility Polygon Queries for Points in Polygons Without Holes: O(log n + k) Query Algorithm With Holes: O(n) Query Algorithm Path Queries Between Points in Simple Polygons Shortest Paths: O(log n + k) Query Algorithm Link Paths: O(log n + k) Query Algorithm 1.1 1 -- 1.2 2 -- 1.3 5 -- 1.4 6 -- 1.5 8 -- 1.6 11 -- 2 13 -- 2.1 13 -- 2.2 16 -- 2.2.1 16 -- 2.2.2 23 -- 2.3 31 -- 2.4 38 -- 3 46 -- 3.1 46 -- 3.2 51 -- 3.3 58 -- 3.3.1 58 -- 3.3.2 65 -- 3.4 66 -- 3.5 68 -- 3.5.1 68 -- 3.5.2 73 -- 3.6 82 -- 3.6.1 82 -- 3.6.2 87 -- 3.7 95 -- 4 105 -- 4.1 105 -- 4.2 108 -- 4.3 110 -- 4.4 113 -- 4.5 115 -- 4.6 124 -- 5 136 -- 5.1 136 -- 5.2 138 -- 5.3 143 -- 5.3.1 143 -- 5.3.2 146 -- 5.4 161 -- 5.4.1 161 -- 5.4.2 165 -- 6 171 -- 6.1 171 -- 6.2 174 -- 6.2.1 174 -- 6.2.2 180 -- 6.3 183 -- 6.4 187 -- 6.4.1 187 -- 6.4.2 195 -- 6.5 201 -- 6.6 205 -- 6.7 208 -- 6.8 214 -- 7 218 -- 7.1 218 -- 7.2 221 -- 7.2.1 221 -- 7.2.2 224 -- 7.3 231 -- 7.4 238 -- 7.5 242 -- 7.5.1 242 -- 7.5.2 248 -- 8 255 -- 8.1 255 -- 8.2 259 -- 8.3 267 -- 8.3.1 267 -- 8.3.2 272 -- 8.4 278 -- 8.4.1 278 -- 8.4.2 289.
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.