Visibility Algorithms in the Plane

Ghosh S.K.0511286260, 0511284721

A human observer can effortlessly identify visible portions of geometric objects present in the environment. However, such 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 in computational geometry over the last three decades. 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. Readers need only a background in algorithms and data structures for understanding this book, and some algorithms from the book can be used in a first course in computational geometry.

---

Table of contents :
Half-title……Page 3
Title……Page 5
Copyright……Page 6
Dedication……Page 7
Contents……Page 9
Preface……Page 13
Prerequisites……Page 14
Acknowledgments……Page 15
1.1 Notion of Visibility……Page 17
1.2 Polygon……Page 18
1.3 Asymptotic Complexity……Page 21
1.4 Triangulation……Page 22
1.5 The Art Gallery Problem……Page 24
1.6 Special Types of Visibility……Page 27
2.1 Problems and Results……Page 29
2.2.1 Non-Winding Polygon: O(n) Algorithm……Page 32
2.2.2 Removing Winding: O(n) Algorithm……Page 39
2.3 Computing Visibility of a Point in Polygons with Holes……Page 47
2.4 Recognizing Simple Polygons Visible from a Point……Page 54
2.5 Notes and Comments……Page 59
3.1 Problems and Results……Page 62
3.2 Characterizing Weak Visibility……Page 67
3.3.1 Scanning the Boundary: O(n log n) Algorithm……Page 74
3.3.2 Using Shortest Path Trees: O(n) Algorithm……Page 81
3.4 Computing Weak Visibility in Polygons with Holes……Page 82
3.5.1 Using Visibility Graph: O(E) Algorithm……Page 84
3.5.2 Scanning the Boundary: O(n) Algorithm……Page 89
3.6.1 In Simple Polygons: O(n) Algorithm……Page 98
3.6.2 In Weak Visibility Polygons: O(n) Algorithm……Page 103
3.7 Recognizing Weakly External Visible Polygons……Page 111
3.8 Notes and Comments……Page 118
4.1 Problems and Results……Page 121
4.2 Characterizing LR-Visibility……Page 124
4.3 Computing LR-Visibility Polygons……Page 126
4.4 Recognizing LR-Visibility Polygons……Page 129
4.5 Walking in an LR-Visibility Polygon……Page 131
4.6 Computing Shortest Path Trees using LR-Visibility……Page 140
4.7 Notes and Comments……Page 151
5.1 Problems and Results……Page 152
5.2 Computing Visibility Graphs of Simple Polygons……Page 154
5.3.1 Worst-Case: O(n2) Algorithm……Page 159
5.3.2 Output-Sensitive: O(n log n + E) Algorithm……Page 162
Plane-Sweep Triangulation……Page 163
The Funnel Sequence……Page 165
The Enhanced Visibility Graph……Page 168
Traversal of Enhanced Visibility Graph……Page 170
The Overall Algorithm……Page 175
5.4.1 Convex Holes: O(n + h2 log h) Algorithm……Page 177
5.4.2 Non-Convex Holes: O(n + h2 log h) Algorithm……Page 181
5.5 Notes and Comments……Page 185
6.1 Problems and Results……Page 187
6.2.1 Necessary Conditions……Page 190
6.2.2 Testing Necessary Conditions: O(n2) Algorithm……Page 196
Special Classes of Graphs……Page 199
Forbidden Induced Sub-graphs……Page 201
Euclidean Shortest Paths……Page 202
6.4.1 Spiral Polygons: O(n) Algorithm……Page 203
6.4.2 Tower Polygons: O(n) Algorithm……Page 211
6.5 Characterizing a Sub-Class of Segment Visibility Graphs……Page 217
6.6 A Few Properties of Vertex-Edge Visibility Graphs……Page 221
6.7 Computing Maximum Clique in a Visibility Graph……Page 224
6.8 Computing Maximum Hidden Vertex Set in a Visibility Graph……Page 230
6.9 Notes and Comments……Page 232
7.1 Problems and Results……Page 234
7.2.1 Using Weak Visibility: O(n) Algorithm……Page 237
7.2.2 Using Complete Visibility: O(n) Algorithm……Page 240
7.3 Computing Minimum Link Paths in Polygons with Holes……Page 247
7.4 Computing Link Center and Radius of Simple Polygons……Page 254
7.5.1 Between Convex Polygons: O(n log k) Algorithm……Page 258
7.5.2 Between Non-Convex Polygons: O(n) Algorithm……Page 264
7.6 Notes and Comments……Page 269
8.1 Problems and Results……Page 271
8.2 Ray-Shooting Queries in Simple Polygons……Page 275
8.3.1 Without Holes: O(log n + k) Query Algorithm……Page 283
8.3.2 With Holes: O(n) Query Algorithm……Page 288
8.4.1 Shortest Paths: O(log n + k) Query Algorithm……Page 294
8.4.2 Link Paths: O(log n + k) Query Algorithm……Page 305
8.5 Notes and Comments……Page 308
Bibliography……Page 311
Index……Page 327