Euclidean Shortest Paths Exact or Approximate Algorithms
The Euclidean shortest path (ESP) problem asks the question: what is the path of minimum length connecting two points in a 2- or 3-dimensional space? Variants of this industrially-significant computational geometry problem also require the path to pass th
- PDF / 6,714,022 Bytes
- 376 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 253 Views
“Beauty on the Path”, a digital painting by Stephen Li (Auckland, New Zealand), September 2011, provided as a gift for this book.
Fajie Li r Reinhard Klette
Euclidean Shortest Paths Exact or Approximate Algorithms
Fajie Li School of Information Science and Technology Huaqiao University P.O. Box 800 Xiamen Fujian People’s Republic of China [email protected]
Reinhard Klette Dept. Computer Science University of Auckland P.O. Box 92019 Auckland 1142 New Zealand [email protected]
ISBN 978-1-4471-2255-5 e-ISBN 978-1-4471-2256-2 DOI 10.1007/978-1-4471-2256-2 Springer London Dordrecht Heidelberg New York British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library Library of Congress Control Number: 2011941219 © Springer-Verlag London Limited 2011 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licenses issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc., in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. Cover design: VTeX UAB, Lithuania Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
To Zhixing Li, and to the two youngest in the Klette family in New Zealand
Foreword
The world is continuous the mind is discrete. David Mumford (born 1937)
Recently, I was confronted with the problem of planning my travel from Israel to New Zealand, home of the two authors of this book. When taking two antipodal points on the globe, like Haifa and Queenstown, there is an infinite number of shortest paths connecting these points. Still, due to constraints like reachable airports and airlines, finding the optimal solution was almost immediate. Throughout the long history of geometry sciences, the problem of finding the shortest path in various scenarios occupied the minds of researchers in many fields. Even in Euclidean spaces, which are considered simple, the introduction of obstacles leads to challenging problems for which efficient computational solvers are hard to find. The optimal path in 3D space with polyhedral obstacles was among the first geometric problems proven to be, at least formally, computationally hard to solve. It took almost 20 years for a team of 5 programming experts to eventually impl
Data Loading...
