Главная    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
Предметный указатель
$\mathcal{O}$-staircase path      11
$\mathcal{O}$-visibility      11
$\mathcal{O}$-visible      11
3-clique ordering      172 185
3-tree      172
Abello, J.      171 172 174 178 183 185 186
Adegeest, J.      221
Agarwal, P. K.      12 173 253 256
Aggarwal, A.      9 170 220 242 250 289 291 292
Aho, A.      31 35 36 64 66 86 285
Aleksandrov, L.      102 220
Algorithm, approximation      10
Algorithm, on-line      135
Algorithm, optimal      6
Algorithm, output-sensitive      137
Algorithm, parallel      5—6 43—44 103 169 254 293
Algorithm, query      259 267 272 278 289
Algorithm, sequential      5
Algorithm, set-union      276
Alon, N.      173
Alsuwaiyel, M. H.      220
Amato, N.      170
Andreae, T.      173
Angular sweep      32—34 36
Apex of a funnel      82 140 150 168 195
Approximation ratio      10
APX-hard      10
Arkin, E.      107 220 221 258 259
Aronov, B.      44 173 257
Arrangement of line segments      4 13 234
Arrangement of lines      146
Arrangement of psuedo-lines      173
Art Gallery Problem      2 8 46 173
Asano, Ta.      8 15 67 137 255 257 272
Asano, Te.      8 13 15 31 67 137 138 143 162 164 169 231 255—257 272 273
Asteroidal triple      190
Atallah, M.      6 43 259
Avis, D.      8 9 14 46 49 50 96 209 217
Bar-Yehuda, R.      8 138 166 168
Base of a funnel      82 150 167 195
Ben-Moshe, B.      170
Benedikt, M.      14
Bertolazzi, P.      43
Bhadury, J.      220
Bhattacharya, B. K.      8 15 23 49—51 57 73 95 105—108 113 115 120 122—124 173 174 208 214
Biedl, T.      253
Bilinear function      245
Bjorling-Sachs, I.      9
Boissonnat, J.      254
Bondy, J.      202
Booth, H.      220 242 250 289 291 292
Booth, K.      191 194 195
Bose, P.      256 257 267
Bounded curvature path      253
Bounding chord      73—82 113—124
Brahma, S.      44
Brandstadt, A.      196 197 200
Breen, M.      11
Bremner, D.      11 173
Briggs, A.      2 102
Brunn, H.      2 4
Buckinghan, M.      184
C-polygon      115—124
C-polygon, clockwise      57 58 73—82 110
C-polygon, counterclockwise      57 58 73—82 110
Canny, J.      2
cell      233
Ch, J.      190
Chain, front      262
Chain, lower      150 162 175 182 282
Chain, method      293
Chain, opposite      108
Chain, same      108
Chain, side      262
Chain, upper      150 162 175 182 282
Chakrabarti, P.      135
Chan, E.      170 220 250
Chandrasekran, R.      220
Chandru, V.      104 220 226 229 244—246 254 291 292
Chang, R.      170
Chazelle, B.      8 48 49 82 84 138 146 166 168 221 224 251 252 256 259 264 269 273 277 279 288 291 293
Chein, O.      51
Chen, C. Y.      172
Chen, D. Z.      6 43—44 49 104 258 259
Chiang, Y.      258
Chin, F.      170
Choi, S.      172
Chord      49 174 180
Chou, S.      12
Chromatic number      184
Chvatal, V.      9
Chwa, K.      8 44 50 135 172
Clarkson, K. L.      170
Cohen, M.      2
Cole, R.      43 293
Colley, P.      172 195
Competitive ratio      135
Complexity, asymptotic      5
Complexity, operations      5
Complexity, polylogarithmic time      6
Complexity, polynomial time      5
Complexity, processor number      6
Complexity, space      5
Complexity, time      5
Component, non-redundant      57 58
Component, redundant      57 58
Conductor      191 194
Convex, hull      16 95 165 202 230 249
Convex, link path      226
Convex, path      226
Convex, quadrilateral      9 201
Convex, quadrilaterization      9
Convex, set      103 229
Cormen, T. H.      5
Cornell, D. G.      171 172 174 178 183 185—187 194
Corridor      167
Coullard, C      183
Coullard, C.      172 173 185
Counter-example      174 178 179 183
Crass, D.      44
Cross-tangent      92 127 266 283
Cross-visible sub-graph      197 200
Culberson, J.      11
Cutset of a graph      202
Cycle, Hamiltonian      172 174 184 188 198 208 214 216
Cycle, ordered      174 180 184
Cycle, outer      186
Cycle, unordered      184
Daescu, O.      258
Das, G.      49 50 57 73 106 221 259
Dasgupta, D.      220
Dasgupta, P.      135
Datta, A.      135
Davis, A.      44
Davis, L.      14
de Berg, M.      221 259
de Rezende, P.      170 259
De Sarkar, S.      135
Dean, J.      12
Decomposition of a polygon      279
Decomposition, balanced      279
Decomposition, tree      279
Delete operation      33 35—37 164
den Berg, M.      169
Dey, T.      44
Diagonal      6 82 278
Diagonal depth      280
Diagonal height      281
Diagonal lower      162
Diagonal principal separating      281—288
Diagonal separating      281
Diagonal upper      162
Djidjev, H.      102 218—220 254
Dobkin, D.      2 292
Doh, J.      50
Donald, B.      2 102
Dorward, S. E.      1 2 13
Downward point      25—29
Dual of a planar subdivision      271
Dual of a triangulation      6 82 85 166
Dual of an arrangement      146
Duality, point-line      256 257 273
Eave      56 224 226 252 290
Edelsbrunner, H.      9 146 162 234 236 256 259 262 269 272 273 293
Edge, active      32 35
Edge, constructed      13 222 232 236 267—272
Edge, convex      53—56 58
Edge, extension      141 224
Edge, forward      18
Edge, incoming      211
Edge, inward      61 64
Edge, left constructed      69 141 267
Edge, outgoing      211
Edge, potential      68
Edge, right constructed      69 141 267
Edge, valid pair      211
Efrat, A.      10
Egecioglu, O.      172
Eidenbenz, S.      10 174
ElGindy, H.      8 14 48 103 172 217 218 258 259
Envelope      99—102
Equivalent order type      173
Evader      44
Even, S.      196
Everett, H.      171—174 178 183 185—187 194 201
Face      234
Fan      184 209
Fan, convex      173 184 209 214 216
Fan, vertex      184 209 214 216
Faugeras, O.      2
Fink, E.      11
Fisk, S.      9
Fixed point      245
Forbidden sub-graph      172 185
Fournier, A.      8 173
Fractional cascading      256 259 264 293
Fredman, M. L.      138 162 166 168
Fulkerson, D. R.      189
Funnel      82 140 150 167 195 258 278
Funnel, linear order      151
Funnel, sequence      147 149 151 236
Funnel, splitting      83—87
Gabor, C. P.      184
Gabow, N. H.      160 276
Garcia-Lopez, J.      12
Garey, M. R.      7
Geodesic center      169
Geodesic diameter      169 261
Geodesic distance      169
Geodesic height      261
Geodesic path      169
Geodesic tree      261
Geodesic triangle      256 259—267
Gewali, L.      12
Ghodsi, M.      257
Ghosh, S. K.      8 10 13 15 23 43 45 49 50 54—56 67 68 72—74 80 87 102—106 108 113 123 124 135 137 138 146 171 172 174 178—180 183 186 208 214 215 218 220 224 226 229 236 237 244—246 248—250 252 254 274 277 289 291 292
Gigus, Z.      2
Gilmore, P. C.      191
Golumbic, M. C.      184 189 190
Goodrich, M. T.      6 43 103 104 169 293
Goswami, P.      173 174 208 214
Graham, R. L.      16 51 95 101 249 250
Graph, 3-connected      172 185 204
Graph, 4-connected      202
Graph, acyclic directed      146
Graph, assignment      178 187
Graph, bipartite      195 196 200 205
Graph, characterization      172 183 187 201 205
Graph, chord      174 180
Graph, chordal      172 184 189
Graph, circle      172 184
Graph, complete      173
Graph, cover      192
Graph, directed      275
Graph, factor      280
Graph, interval      172 187 190 194
Graph, k-connected      202
Graph, layered directed      292
Graph, perfect      172 184 187
Graph, permutation      195 196 200
Graph, planar      172 201
Graph, quasi-persistent      186
Graph, recognition      171 174 179 187 195 200 201 205
Graph, Reconstruction      171
Graph, sparse      170
Graph, triangulated      202
Greedy path      229 230 243 247 289
Grigni, M.      256 259
Gross, O. A.      189
Gruber, P. M.      4
Guard, edge      8—10
Guard, mobile      8 9
Guard, point      8—10
Guard, stationary      8 9
Guard, vertex      8—10
Guerra, C.      43
Guha, S.      103 104 169 293
Guibas, L. J.      15 44 48 49 53 65 67 82 106 110 112 113 137 139 143 146 220 224 234 236 240 255—259 262 264 272 273 277—279 288 290 292 293
Gy?ori, E.      9
Half-plane, exterior      38—40 42
Half-plane, interior      38—40 42 43
Hall-Holt, O.      170
Halperin, D.      169
Har-Peled, S.      10
Haralick, R. M.      136
Heffernan, P. J.      15 49 50 105—108 115
Held, M.      107
Hershberger, J.      15 48 49 53 65 67 72 82 103 104 106 110 112 113 127 137—139 143 169 170 206 218 220 221 224 230 240 241 255—259 264 272 278 279 288 290 292 293
Hertel, S.      8
Hidden vertex set      173
Hoang, C. T.      173 201
Hoffman, A. J.      191
Hoffmann, F.      9
Hoffmann, K.      24
Hoffmann, M.      173
Hole, convex      161
Hole, non-convex      165 169
Homotopy      220
Hopcroft, J. H.      31 35 36 64 66 86 285
Hourglass      157 167 256 258 278—289
Hourglass, closed      282
Hourglass, open      282
Hsu, F.      170
Hsu, W.      184
Icking, C.      49 105 107 108 110 115 117 135
Imai, H.      15 67 137 173 255 257 272
Incerpi, J.      8
Induced path      192
Induced sub-graph      183 185 189 208
INSERT operation      33 35—37 164
interval      243 289
Interval, left      70
Interval, right      70
Inverse Ackermann function      218
Isomorphism of graphs      174 216
Isomorphism of polygons      253
Jackson, L.      173
Joe, B.      14
Johnson, D. S.      7
Junction triangle      167
1 2 3
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2017
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте