Computational Geometry An Introduction Through Randomized Algori....pdf-资料库

bigarm-8792645-16359647568891459753.pdf-第1页.png

第1页 / 共461页

bigarm-8792645-16359647568891459753.pdf-第2页.png

第2页 / 共461页

bigarm-8792645-16359647568891459753.pdf-第3页.png

第3页 / 共461页

bigarm-8792645-16359647568891459753.pdf-第4页.png

第4页 / 共461页

bigarm-8792645-16359647568891459753.pdf-第5页.png

第5页 / 共461页

bigarm-8792645-16359647568891459753.pdf-第6页.png

第6页 / 共461页

bigarm-8792645-16359647568891459753.pdf-第7页.png

第7页 / 共461页

bigarm-8792645-16359647568891459753.pdf-第8页.png

第8页 / 共461页

Computational Geometry An Introduction Through Randomized Algorithms Ketan Mulmuley

Computational Geometry An Introduction Through Randomized Algorithms Ketan Mulmuley The University of Chicago PRENTICE HALL, Englewood Cliffs, NJ 07632

Library of Congress Cataloging-in-Publication Data Mulmuley, Ketan. Computational geometry: an introduction through randomized algorithms / Ketan Mulmuley. p. cm. Includes bibliographical references and index. ISBN 0-13-336363-5 1. Geometry--Data processing. 2. Algorithms. I. Title. QA448.M85 1994 516'.13--dc2O 93-3138 CIP Acquisitions editor: BILL ZOBRIST Production editor: JOE SCORDATO Copy editor: PETER J. ZURITA Prepress buyer: LINDA BEHRENS Manufacturing buyer: DAVID DICKEY Editorial assistant: DANIELLE ROBINSON C) 1994 by Prentice-Hall, Inc. A Simon & Schuster Company Englewood Cliffs, New Jersey 07632 All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs. Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 ISBN 0-13-336363-5 Prentice-Hall Intemational (UK) Limited, London Prentice-Hall of Australia Pty. Limited, Sydney Prentice-Hall Canada Inc., Toronto Prentice-Hall Hispanoamericana, S.A., Mexico Prentice-Hall of India Private Limited, New Delhi Prentice-Hall of Japan, Inc., Tokyo Simon & Schuster Asia Pte. Ltd., Singapore Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro

For Sanchit

Contents Preface Notation I Basics ix xvi 1 1 Quick-sort and search ............................. 1.1 Quick-sort ......... 1.2 Another view of quick-sort . . 1.3 Randomized binary trees .... 3 4 5 7 11 1.3.1 Dynamization ................................... 1.3.2 Another interpretation of rotations ..................... 13 18 ............................................. . . . . . . . . . . . . . . . . . . ................................. 1.4 Skip lists 2 What is computational geometry? 2.1 Range queries ..... 2.2 Arrangements ........................................ 2.3 Trapezoidal decompositions 2.4 Convex polytopes ...... ......................................... ............................. .... ..................................... 2.4.1 Duality ........................................ 2.5 Voronoi diagrams ...................................... 2.6 Hidden surface removal . . . . . . . . . . . . . . . . . . . . . 2.7 Numerical precision and degeneracies ...................... 2.8 Early deterministic algorithms ... ............ ........................... 2.8.1 Planar convex hulls ......................... 2.8.2 Arrangements of lines 2.8.3 Trapezoidal decompositions 2.8.4 Planar Voronoi diagrams ..................... 2.8.5 Planar point location ........................ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Deterministic vs. randomized algorithms ................... v 26 28 29 32 36 40 46 51 52 55 56 58 61 67 74 78

vi CONTENTS 2.10 The model of randomness ..... ............................... 78 3 Incremental algorithms 3.1 Trapezoidal decompositions 3.1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . .............. 3.1.2 Planar graphs .... 3.1.3 Simple polygons* ................................ .............................. ................................... 81 84 90 94 94 96 99 ....................................... 103 104 106 111 120 ....................... . . . . ............................. . . . . . . . . . . . . . . . . . . . . 3.2 Convex polytopes ...................................... ...... 3.2.1 Conflict maintenance ..... 3.2.2 History 3.2.3 On-line linear programming .... . . 3.3 Voronoi diagrams . . 3.4 Configuration spaces . 3.5 Tail estimates* . . ....................................... .. . . . . . . . . . . . . . . . . . ... ......................... ............................. 126 129 132 135 ................................. 137 140 142 149 151 158 162 167 .......................... . . . . . . . . . . . 4 Dynamic algorithms 4.1 Trapezoidal decompositions ... 4.1.1 Point location .................................. 4.2 Voronoi diagrams ... ..................................... 4.2.1 Conflict search ..... 4.3 History and configuration spaces 4.3.1 Expected performance* 4.4 Rebuilding history 4.5 Deletions in history .... .................................... ................................... 3D convex polytopes ............................ 4.5.1 4.5.2 Trapezoidal decompositions . . . .................................... . 4.6 Dynamic shuffling 5 Random sampling 5.1 Configuration spaces with bounded valence . . 5.2 Top-down sampling . 5.2.1 Arrangements of lines . . . . 5.3 Bottom-up sampling .................................. 5.3.1 Point location in arrangements 5.4 Dynamic sampling .................................... 5.4.1 Point location in arrangements . . . . . . . . . . . . . .................... ................ . . . ............................ 173 176 181 182 184 185 192 193 ................................... 197 . . 201 204 210 215 221 . . ......... ................. ............................... .................... . . . . . 5.5 Average conflict size .... 5.6 More dynamic algorithms . 5.6.1 Point location in trapezoidal decompositions 5.6.2 Point location in Voronoi diagrams .. . . . . . . . . . . 5.7 Range spaces and E-nets ..... 5.7.1 VC dimension of a range space .................

vii 223 227 CONTENTS 5.8 Comparisons .......................................... II Applications 6 Arrangements of hyperplanes Incremental construction ..... 6.1 6.2 Zone Theorem ....................................... 6.3 Canonical triangulations ........................... 6.3.1 Cutting Lemma ............................ 6.4 Point location and ray shooting ...................... 6.4.1 Static setting ............................... 6.4.2 Dynamization... ........................... 229 ............................... 232 234 238 241 242 242 248 250 253 .. ......................... .. ........................... 6.5 Point location and range queries 6.5.1 Dynamic maintenance 7 Convex polytopes 7.1 Linear programming 7.2 The number of faces .................................. .................................. 7.2.1 Dehn Sommerville relations ... ....................... 7.2.2 Upper bound theorem: Asymptotic form ............ 7.2.3 Upper bound theorem: Exact form .. ................. 7.2.4 Cyclic polytopes ................................ Incremental construction ..... 7.3.1 Conflicts and linear programming .................. 7.3.2 Conflicts and history ............................ 7.3 7.4 The expected structural and conflict change ................ 7.5 Dynamic maintenance ................................. 7.6 Voronoi diagrams .. 7.7 Search problems ..................................... .... ...................................... 7.7.1 Vertical ray shooting . . . . . . . . 7.7.2 Half-space range queries .......................... 7.7.3 Nearest k-neighbor queries 7.7.4 Dynamization .................................. .. 7.8 Levels and Voronoi diagrams of order k 260 262 267 268 271 271 274 ............................... 276 278 279 280 284 285 286 . . . . . . . . . . . 288 289 291 292 294 301 306 ................... .. ......................... ........................ 7.8.1 7.8.2 Incremental construction Single level .................................... 8 Range search 8.1 Orthogonal intersection search . . . . . . . . . . . . . . . . . 8.1.1 Randomized segment tree 8.1.2 Arbitrary dimension ......................... ........................ 311 311 312 317

viii CONTENTS 8.2 Nonintersecting segments in the plane ................. 8.3 Dynamic point location ...... 8.4 Simplex range search ............................. ..................... 8.4.1 Partition theorem. 8.4.2 Preprocessing time..................... .................... 8.5 Half-space range queries ........................... .................... 8.5.1 Partition theorem. 8.5.2 Half-space emptiness ........................ 8.6 Decomposable search problems ...................... 8.6.1 Dynamic range queries ....................... 8.7 Parametric search .. . ....................... 9 Computer graphics 9.1 Hidden surface removal ...... ..................... 9.1.1 Analysis. . ......................... 9.2 Binary Space Partitions ........................... ...................... ..................... ....................... 9.2.1 Dimension two. 9.2.2 Dimension three. . 9.3 Moving viewpoint .. 9.3.1 Construction of a cylindrical partition.......... 9.3.2 Randomized incremental construction.......... 10 How crucial is randomness? 10.1 Pseudo-random sources ...... 10.2 Derandomization ............................... 10.2.1 E-approximations...................... 10.2.2 The method of conditional probabilities......... 10.2.3 Divide and conquer ......................... ..................... A Tail estimates A.1 Chernoff's technique ........................ A.1.1 Binomial distribution................... A.1.2 Geometric distribution ................... A.1.3 Harmonic distribution................... A.2 Chebychev's technique ............................ Bibliography Index 322 327 328 332 336 338 341 343 345 348 349 358 361 367 372 372 379 383 391 392 398 399 410 412 413 417 422 423 424 426 428 429 431 442

资料库

Computational Geometry An Introduction Through Randomized Algori....pdf

相关推荐

课程资源

热门标签

最新资料