Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Ghosh S.K. — Visibility Algorithms in the Plane
Ghosh S.K. — Visibility Algorithms in the Plane



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Visibility Algorithms in the Plane

Автор: Ghosh S.K.

Аннотация:

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.


Язык: en

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2007

Количество страниц: 350

Добавлена в каталог: 30.12.2007

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Reflection, specular      44
Reif, J. H.      258
Relation      274
Relative convex hull      166 235 251
Reverse greedy path      244
Reverse turn      60 88 96 126
Revolution number      14 23 38 58
Rippel, J.      173
Rivest, R. L.      5
Robbins, S.      253
Rohnert, H.      138 161 165 168
Rosenstiehl, P.      24
Rote, G.      218 219 231
s-deadlock      117—124
Sack, J.      9 12 49 102 218—221 238 254 259
Saluja, S.      8 49 50 54—56 68 72—74 80 87 104 105 124 135 174 215 226 229 244—246 254 291 292
Salza, S.      43
Same type      25—29
Sampson, J.      170
Sanderson, A. C.      2
Saran, H.      11
Sarkar, D.      44
Sarnak, N.      293
Schiuerer, S.      11
Schorr, A.      137
Schuierer, S.      11 135 221 259
Search, binary      64 85 284 285
Search, linear      64 84
Seidel, R.      2 146 219 238 273
Semrau, I.      135
Separating path      203
Set-union operation      257
Shamos, M. I.      5 39 92 96 148 149 255 285 286
Shapiro, L. G.      136
Sharir, M.      12 48 49 53 65 82 106 110 112 113 137 139 143 169 219 224 234 236 238 240 256 257 259 264 279 288
Shauck, S.      103 104 169 293
Shermer, T.      2 9—11 13 15 23 173 174 208 214 253
Shin, C.      135
Shin, S.      8 49 50 135 172
Shor, P.      170
Shortest path      49 51—55 103 138—169 176 186 187 215 224 251 258 259 278—289 293
Shortest path, map      141 224 241
Shortest path, tree      49 82 103 111 207 224 229 240 258
Simov, B.      44
Simpson, R. B.      14
Skiena, S.      107 172—174 214 217
Slab method      292
Sleator, D.      135
Sleeve      167
Slutzki, G.      44
Smallest path      259
Snoeyink, J.      218 220 221 224 230 256 259
Sorted angular order      4 17 21 43 249 257 272 276
Souvaine, D. L.      9
Spinrad, J.      172 195—197 200
Srinivasaraghavan, G.      171 173 178
Staircase path      11
Stein, C.      5
Steinberg, L.      51
Stewart, L.      196 197 200
Stolfi, J.      262 293
Storer, J. A.      258
Straight path      192 194
Street      105 135
Streinu, I.      171—174 179 205
Strong ordering      196
Sub-graph      183
Supowit, K. J.      10 184
Suri, S.      15 49 66 169 170 173 218—221 224 231 233 238 242 250 253 256 258 259 289 291 292
Suzuki, I.      44
t-deadlock      117—124
tail      260
Tamassia, R.      173 258
Tangent      161 166 265 283
Tangent, left      227 242
Tangent, lower      162
Tangent, right      227 242
Tangent, upper      163
Tarjan, R. E.      7 8 24 48 49 53 65 82 106 110 112 113 135 138 139 143 160 162 166 168 224 240 256 257 264 276 279 288 293
Tazoe, Y.      44
Teichmann, M.      257
Teller, S.      2
Theorems, hidden vertex set      216
Theorems, link center computation      242
Theorems, link diameter computation      242
Theorems, link path computation      224 231 238
Theorems, link path query      292
Theorems, link radius computation      242
Theorems, LR-visibility characterization      108
Theorems, LR-visibility computation      113
Theorems, LR-visibility recognition      115
Theorems, maximum clique      214
Theorems, nested polygon      245 248 249 251 252
Theorems, point visibility computation      23 35 38
Theorems, point visibility query      269 272 278
Theorems, point visibility recognition      43
Theorems, polygon triangulation      8 149
Theorems, polygon walk      117 122 124
Theorems, polygon winding      31
Theorems, ray-shooting query      262 267
Theorems, shortest path computation      138 165 169
Theorems, shortest path query      286 289
Theorems, shortest path tree computation      85 87 95 134
Theorems, visibility graph computation      143 146 161 165 168
Theorems, visibility graph construction      207 208
Theorems, visibility graph recognition      183 194 195 197 201 205
Theorems, weak visibility characterization      55 56
Theorems, weak visibility computation      64 66 68
Theorems, weak visibility recognition      73 82 102
Tietze, H.      4
Tokarsky, G.T.      44
Tollis, I.      173
Topological sorting      146 276
Toth, C.,      173
Toussaint, G. T.      8 9 46 48—51 53 95 96 103 169 170 173 219 238
Trapezoid method      293
Traversal, depth-first      194
Traversal, postorder      151
Traversal, preorder      151
TREE      6
Tree, balanced      32 34 163
Tree, binary      31 34
Tree, decomposition      279
Tree, finger search      86 160
Tree, free      261 263
Tree, geodesic      261
Tree, height      31
Tree, height balanced      149 285
Tree, level-linked      24
Tree, lower      151
Tree, search      85 86
Tree, upper      151
Tree, weight-balanced binary      259 263
Tree, window      258
Triangulation of a polygon      6 82 103 224 251 274 278
Triangulation, balanced geodesic      259
Triangulation, Hamiltonian      107 188
Triangulation, plane sweep      147
Tseng, L. H.      106 107 115
Tu, H.      259
Turning point      222 227 232 243 289
Ullman, J. D.      31 35 36 64 66 86 285
Umemoto, H.      44
Update operation      33 35—37
Upper node      287
Upward point      25—29
Urrutia, J.      2 9 10
Vaidya, P.      170
Valentine, F. A.      4
Van Wyk, C. J.      8
Vegter, G.      137 138 169 257
Veni Madhavan, C. E.      8 49 50 54—56 68 72—74 80 87 103 105 124 174 215 220
Vertex, antipodal      96—102
Vertex, blocking      175 181 192 208 210
Vertex, consecutive visible      180
Vertex, convex      2
Vertex, cut      202
Vertex, furthest adjacent      211
Vertex, labeled      198
Vertex, overlaying      193 194
Vertex, reflex      2
Vertex, simplicial      189
Vertex, unlabeled      198
Vertical ordering      147
Visibility graph      136 161 169—171 174 183 187 195 200 206 208 214 216 218 234 236 238
Visibility graph, edge-edge      173 208
Visibility graph, enhanced      147 152
Visibility graph, non-isomorphic      216
Visibility graph, point      173
Visibility graph, segment      173 201 205
Visibility graph, tangent      161 165 168
Visibility graph, vertex      206
Visibility graph, vertex-edge      173 205 208
Visibility polygon of a point      13 16 43 124 221 231 249 255 267—278
Visibility polygon of a segment      49 232
Visibility polygon of a set      102
Visibility polygon, complete      47 48 103 229
Visibility polygon, external      51 95—102
Visibility polygon, LR      105—135
Visibility polygon, weak      47—49 51—55 58 64 66 68 73 75—77 87 103 222 257
Visibility, cell      256 267—272
Visibility, chord      49 50 68 72—82 87
Visibility, circular      12
Visibility, clear      11
Visibility, complete      46 49 218 224 250
Visibility, complex      257
Visibility, external      50
Visibility, k      220 238
Visibility, LR      105—135
Visibility, omni-directional      44
Visibility, rectangular      11 12
Visibility, staircase      11
Visibility, strong      46
Visibility, weak      46 48 49 59 103 218 221
Visibility, with reflection      44
Visibility, X-ray      12
Visible apex      155
Visible clearly      11
Visible rectangularly      12
Visible segment      139 143 195 201
Visible staircase      11
Visible X-ray      12
Voronai diagram      169
Wagner, H.      43
Walk      107—108 115—124
Walk, discretely straight      107
Walk, straight      107
Walkable      107
Wallace, J.      2
Wang, C. A.      170 220 250
Watchman tour      220 221
wedge      39 249
Wein, R.      169
Welzl, E.      9 67 137 143
Wesley, M. A.      2 51 136
Whitesides, S.      219 238 253
Wills, J. M.      4
Window      148
Window partition      238 241
Wismath, S.      173
Woeginger, G.      218 219 231
Woo, R. C.      12
Woo, T. C.      8 49
Wood, D.      11 12
Wu, Y. F.      170 259
Yamamoto, P.      11
Yamashita, M.      44
Yao, F. F.      16 51 95 101 249 250
Yap, C. K.      103 219 220 238 242 250 289 291 292
Zarei, A.      257
Zhang, L.      257
Zhang, Z.      44
1 2 3
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте