文档介绍：Computational
Geometry
An Introduction
Franco P. Preparata
Michael Ian Shamos
With 234 Illustrations
Springer-Verlag
New York Berlin Heidelberg London Paris
Tokyo Hong Kong Barcelona Budapest
Franco P. Preparata Michael Ian Shamos
Department puter Science Department puter Science
Brown University Carnegie-Mellon University
Providence, RI 02912 Pittsburgh, PA 15213
. .
Series Editors:
David Gries Fred Schneider
Department puter Science Department puter Science
Cornell University Cornell University
Upson Hall Upson Hall
Ithaca, NY 14853-7501 Ithaca, NY 14853-7501
. .
Library of Congress Cataloging in Publication Data
Preparata, Franco P.
Computational geometry.
(Texts and monographs puter science)
Bibliography: p.
Includes index.
1. Geometry—Data processing. I. Shamos, Michael.
II. Title.
III. Series.
1985
516'.028'54
85-8049
Printed on acid - free paper.
© 1985 by Springer-Verlag New York Inc.
All rights reserved. No part of this book may be translated or reproduced in any form
without written permission from Springer-Verlag, 175 Fifth Avenue, New York, New
York 10010, .
Typeset by Asco Trade Typesetting Ltd., Hong Kong.
Printed and bound by R. R. Donnelley & Sons, Harrisonburg, Virginia.
Printed in the United States of America.
9 8 7 6 5 (corrected printing)
ISBN 0-387-96131-3 Springer-Verlag New York Berlin Heidelberg Tokyo
ISBN 3 - 540 - 96131 - 3 Springer-Verlag Berlin Heidelberg New York Tokyo
To Paola and Claudia
and
To Julie
Preface to the Second Printing
The second printing of this book offers an excellent opportunity to correct
the (forgivable) typos and the (less forgivable) imprecisions or minor errors of
the first edition. Moreover, in the three years intervening between the two
printings, some problems that were then open have been essfully solved
and some techniques, which had just been disclosed at the ti