Visibility algorithms in the plane

Subir Kumar Ghosh0521875749, 9780521875745, 9780511286261

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.

---

Table of contents :
Half-title……Page 3
Title……Page 5
Copyright……Page 6
Dedication……Page 7
䌀漀渀琀攀渀琀猀……Page 9
倀爀攀昀愀挀攀……Page 13
倀爀攀爀攀焀甀椀猀椀琀攀猀……Page 14
䄀挀欀渀漀眀氀攀搀最洀攀渀琀猀……Page 15
㄀⸀㄀ 一漀琀椀漀渀 漀昀 嘀椀猀椀戀椀氀椀琀礀……Page 17
㄀⸀㈀ 倀漀氀礀最漀渀……Page 18
㄀⸀㌀ 䄀猀礀洀瀀琀漀琀椀挀 䌀漀洀瀀氀攀砀椀琀礀……Page 21
㄀⸀㐀 吀爀椀愀渀最甀氀愀琀椀漀渀……Page 22
㄀⸀㔀 吀栀攀 䄀爀琀 䜀愀氀氀攀爀礀 倀爀漀戀氀攀洀……Page 24
㄀⸀㘀 匀瀀攀挀椀愀氀 吀礀瀀攀猀 漀昀 嘀椀猀椀戀椀氀椀琀礀……Page 27
㈀⸀㄀ 倀爀漀戀氀攀洀猀 愀渀搀 刀攀猀甀氀琀猀……Page 29
2.2.1 Non-Winding Polygon: O(n) Algorithm……Page 32
2.2.2 Removing Winding: O(n) Algorithm……Page 39
㈀⸀㌀ 䌀漀洀瀀甀琀椀渀最 嘀椀猀椀戀椀氀椀琀礀 漀昀 愀 倀漀椀渀琀 椀渀 倀漀氀礀最漀渀猀 眀椀琀栀 䠀漀氀攀猀……Page 47
㈀⸀㐀 刀攀挀漀最渀椀稀椀渀最 匀椀洀瀀氀攀 倀漀氀礀最漀渀猀 嘀椀猀椀戀氀攀 昀爀漀洀 愀 倀漀椀渀琀……Page 54
㈀⸀㔀 一漀琀攀猀 愀渀搀 䌀漀洀洀攀渀琀猀……Page 59
㌀⸀㄀ 倀爀漀戀氀攀洀猀 愀渀搀 刀攀猀甀氀琀猀……Page 62
㌀⸀㈀ 䌀栀愀爀愀挀琀攀爀椀稀椀渀最 圀攀愀欀 嘀椀猀椀戀椀氀椀琀礀……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
㌀⸀㐀 䌀漀洀瀀甀琀椀渀最 圀攀愀欀 嘀椀猀椀戀椀氀椀琀礀 椀渀 倀漀氀礀最漀渀猀 眀椀琀栀 䠀漀氀攀猀……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
㌀⸀㜀 刀攀挀漀最渀椀稀椀渀最 圀攀愀欀氀礀 䔀砀琀攀爀渀愀氀 嘀椀猀椀戀氀攀 倀漀氀礀最漀渀猀……Page 111
㌀⸀㠀 一漀琀攀猀 愀渀搀 䌀漀洀洀攀渀琀猀……Page 118
㐀⸀㄀ 倀爀漀戀氀攀洀猀 愀渀搀 刀攀猀甀氀琀猀……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
㐀⸀㜀 一漀琀攀猀 愀渀搀 䌀漀洀洀攀渀琀猀……Page 151
㔀⸀㄀ 倀爀漀戀氀攀洀猀 愀渀搀 刀攀猀甀氀琀猀……Page 152
㔀⸀㈀ 䌀漀洀瀀甀琀椀渀最 嘀椀猀椀戀椀氀椀琀礀 䜀爀愀瀀栀猀 漀昀 匀椀洀瀀氀攀 倀漀氀礀最漀渀猀……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
倀氀愀渀攀ⴀ匀眀攀攀瀀 吀爀椀愀渀最甀氀愀琀椀漀渀……Page 163
吀栀攀 䘀甀渀渀攀氀 匀攀焀甀攀渀挀攀……Page 165
吀栀攀 䔀渀栀愀渀挀攀搀 嘀椀猀椀戀椀氀椀琀礀 䜀爀愀瀀栀……Page 168
吀爀愀瘀攀爀猀愀氀 漀昀 䔀渀栀愀渀挀攀搀 嘀椀猀椀戀椀氀椀琀礀 䜀爀愀瀀栀……Page 170
吀栀攀 伀瘀攀爀愀氀氀 䄀氀最漀爀椀琀栀洀……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
㔀⸀㔀 一漀琀攀猀 愀渀搀 䌀漀洀洀攀渀琀猀……Page 185
㘀⸀㄀ 倀爀漀戀氀攀洀猀 愀渀搀 刀攀猀甀氀琀猀……Page 187
㘀⸀㈀⸀㄀ 一攀挀攀猀猀愀爀礀 䌀漀渀搀椀琀椀漀渀猀……Page 190
6.2.2 Testing Necessary Conditions: O(n2) Algorithm……Page 196
匀瀀攀挀椀愀氀 䌀氀愀猀猀攀猀 漀昀 䜀爀愀瀀栀猀……Page 199
䘀漀爀戀椀搀搀攀渀 䤀渀搀甀挀攀搀 匀甀戀ⴀ最爀愀瀀栀猀……Page 201
䔀甀挀氀椀搀攀愀渀 匀栀漀爀琀攀猀琀 倀愀琀栀猀……Page 202
6.4.1 Spiral Polygons: O(n) Algorithm……Page 203
6.4.2 Tower Polygons: O(n) Algorithm……Page 211
㘀⸀㔀 䌀栀愀爀愀挀琀攀爀椀稀椀渀最 愀 匀甀戀ⴀ䌀氀愀猀猀 漀昀 匀攀最洀攀渀琀 嘀椀猀椀戀椀氀椀琀礀 䜀爀愀瀀栀猀……Page 217
㘀⸀㘀 䄀 䘀攀眀 倀爀漀瀀攀爀琀椀攀猀 漀昀 嘀攀爀琀攀砀ⴀ䔀搀最攀 嘀椀猀椀戀椀氀椀琀礀 䜀爀愀瀀栀猀……Page 221
㘀⸀㜀 䌀漀洀瀀甀琀椀渀最 䴀愀砀椀洀甀洀 䌀氀椀焀甀攀 椀渀 愀 嘀椀猀椀戀椀氀椀琀礀 䜀爀愀瀀栀……Page 224
㘀⸀㠀 䌀漀洀瀀甀琀椀渀最 䴀愀砀椀洀甀洀 䠀椀搀搀攀渀 嘀攀爀琀攀砀 匀攀琀 椀渀 愀 嘀椀猀椀戀椀氀椀琀礀 䜀爀愀瀀栀……Page 230
㘀⸀㤀 一漀琀攀猀 愀渀搀 䌀漀洀洀攀渀琀猀……Page 232
㜀⸀㄀ 倀爀漀戀氀攀洀猀 愀渀搀 刀攀猀甀氀琀猀……Page 234
7.2.1 Using Weak Visibility: O(n) Algorithm……Page 237
7.2.2 Using Complete Visibility: O(n) Algorithm……Page 240
㜀⸀㌀ 䌀漀洀瀀甀琀椀渀最 䴀椀渀椀洀甀洀 䰀椀渀欀 倀愀琀栀猀 椀渀 倀漀氀礀最漀渀猀 眀椀琀栀 䠀漀氀攀猀……Page 247
㜀⸀㐀 䌀漀洀瀀甀琀椀渀最 䰀椀渀欀 䌀攀渀琀攀爀 愀渀搀 刀愀搀椀甀猀 漀昀 匀椀洀瀀氀攀 倀漀氀礀最漀渀猀……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
㜀⸀㘀 一漀琀攀猀 愀渀搀 䌀漀洀洀攀渀琀猀……Page 269
㠀⸀㄀ 倀爀漀戀氀攀洀猀 愀渀搀 刀攀猀甀氀琀猀……Page 271
㠀⸀㈀ 刀愀礀ⴀ匀栀漀漀琀椀渀最 儀甀攀爀椀攀猀 椀渀 匀椀洀瀀氀攀 倀漀氀礀最漀渀猀……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
㠀⸀㔀 一漀琀攀猀 愀渀搀 䌀漀洀洀攀渀琀猀……Page 308
䈀椀戀氀椀漀最爀愀瀀栀礀……Page 311
䤀渀搀攀砀……Page 327