@inproceedings{81781ac01297485cb8a5a94c26207998,

title = "Geodesic Fr{\'e}chet distance inside a simple polygon",

abstract = "We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fr{\'e}chet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical efficiency when compared to parametric search. We present the first algorithm for the geodesic Fr{\'e}chet distance between two polygonal curves A and B inside a simple bounding polygon P. The geodesic Fr{\'e}chet decision problem is solved almost as fast as its non-geodesic sibling and requires O(N2log k) time and O(k+N) space after O(k) preprocessing, where N is the larger of the complexities of A and B and k is the complexity of P. The geodesic Fr{\'e}chet optimization problem is solved by a randomized approach in O(k+N2log kN log N) expected time and O(k+N2) space. This runtime is only a logarithmic factor larger than the standard non-geodesic Fr{\'e}chet algorithm (Alt and Godau 1995). Results are also presented for the geodesic Fr{\'e}chet distance in a polygonal domain with obstacles and the geodesic Hausdorff distance for sets of points or sets of line segments inside a simple polygon P.",

author = "{Cook IV}, A.F. and C. Wenk",

year = "2008",

language = "English",

series = "Dagstuhl Seminar Proceedings",

publisher = "Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI)",

pages = "193--204",

editor = "S. Albers and P. Weil",

booktitle = "Proceedings 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008, Bordeaux, France, February 21-23, 2008)",

}