Between Shapes, Using the Hausdorff Distance
Publication date
2020
Authors
van Kreveld, M.J.
Miltzow, Tillmann
Ophelders, Tim
Sonke, Willem
Vermeulen, Jordi
Editors
Cao, Yixin
Cheng, Siu-Wing
Li, Minming
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
Abstract
Given two shapes A and B in the plane with Hausdorff distance 1, is there a shape S with Hausdorff distance 1/2 to and from A and B? The answer is always yes, and depending on convexity of A and/or B, S may be convex, connected, or disconnected. We show a generalization of this result on Hausdorff distances and middle shapes, and show some related properties. We also show that a generalization of such middle shapes implies a morph with a bounded rate of change. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two sets and show how to approximate or compute it.
Keywords
computational geometry, Hausdorff distance, shape interpolation
Citation
van Kreveld, M J, Miltzow, T, Ophelders, T, Sonke, W & Vermeulen, J L 2020, Between Shapes, Using the Hausdorff Distance. in Y Cao, S-W Cheng & M Li (eds), 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, pp. 13:1-13:16. https://doi.org/10.4230/LIPIcs.ISAAC.2020.13