Visibility algorithms in the plane

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