Visibility Algorithms in the Plane

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