DeBerg - Computational Geometry - Algorithms and Applications 3e (Springer, 2008).pdf - Geometry - Kuya

Computational Geometry

Third Edition

Mark de Berg · Otfried Cheong

Marc van Kreveld · Mark Overmars

Computational Geometry

Algorithms and Applications

Third Edition

123

Prof. Dr. Mark de Berg

Department of Mathematics

and Computer Science

TU Eindhoven

P.O. Box 513

5600 MB Eindhoven

The Netherlands

mdberg@win.tue.nl

Dr. Marc van Kreveld

Department of Information

and Computing Sciences

Utrecht University

P.O. Box 80.089

3508 TB Utrecht

The Netherlands

marc@cs.uu.nl

Dr. Otfried Cheong, ne Schwarzkopf

Department of Computer Science

KAIST

Gwahangno 335, Yuseong-gu

Daejeon 305-701

Korea

otfried@kaist.edu

Prof. Dr. Mark Overmars

Department of Information

and Computing Sciences

Utrecht University

P.O. Box 80.089

3508 TB Utrecht

The Netherlands

markov@cs.uu.nl

ISBN 978-3-540-77973-5

e-ISBN 978-3-540-77974-2

DOI 10.1007/978-3-540-77974-2

ACM Computing Classiﬁcation (1998): F.2.2, I.3.5

Library of Congress Control Number: 2008921564

This work is subject to copyright. All rights are reserved, whether the whole or part of the material

is concerned, speciﬁcally the rights of translation, reprinting, reuse of illustrations, recitation,

broadcasting, reproduction on microﬁlm or in any other way, and storage in data banks. Duplication

of this publication or parts thereof is permitted only under the provisions of the German Copyright

Law of September 9, 1965, in its current version, and permission for use must always be obtained

from Springer. Violations are liable for prosecution under the German Copyright Law.

The use of general descriptive names, registered names, trademarks, etc. in this publication does

not imply, even in the absence of a speciﬁc statement, that such names are exempt from the relevant

protective laws and regulations and therefore free for general use.

Cover design: KünkelLopka, Heidelberg

Printed on acid-free paper

987654321

springer.com

Preface

Computational geometry emerged from the ﬁeld of algorithms design and

analysis in the late 1970s. It has grown into a recognized discipline with its

own journals, conferences, and a large community of active researchers. The

success of the ﬁeld as a research discipline can on the one hand be explained

from the beauty of the problems studied and the solutions obtained, and, on the

other hand, by the many application domains—computer graphics, geographic

information systems (GIS), robotics, and others—in which geometric algorithms

play a fundamental role.

For many geometric problems the early algorithmic solutions were either

slow or difﬁcult to understand and implement. In recent years a number of new

algorithmic techniques have been developed that improved and simpliﬁed many

of the previous approaches. In this textbook we have tried to make these modern

algorithmic solutions accessible to a large audience. The book has been written

as a textbook for a course in computational geometry, but it can also be used for

self-study.

Structure of the book. Each of the sixteen chapters (except the introductory

chapter) starts with a problem arising in one of the application domains. This

problem is then transformed into a purely geometric one, which is solved

using techniques from computational geometry. The geometric problem and the

concepts and techniques needed to solve it are the real topic of each chapter. The

choice of the applications was guided by the topics in computational geometry

we wanted to cover; they are not meant to provide a good coverage of the

application domains. The purpose of the applications is to motivate the reader;

the goal of the chapters is not to provide ready-to-use solutions for them. Having

said this, we believe that knowledge of computational geometry is important

to solve geometric problems in application areas efﬁciently. We hope that our

book will not only raise the interest of people from the algorithms community,

but also from people in the application areas.

For most geometric problems treated we give just one solution, even when

a number of different solutions exist. In general we have chosen the solution

that is easiest to understand and implement. This is not necessarily the most

efﬁcient solution. We also took care that the book contains a good mixture of

techniques like divide-and-conquer, plane sweep, and randomized algorithms.

We decided not to treat all sorts of variations to the problems; we felt it is more

important to introduce all main topics in computational geometry than to give

more detailed information about a smaller number of topics.

DeBerg - Computational Geometry - Algorithms and Applications 3e (Springer, 2008).pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: