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.
Original language | English |
---|---|
Title of host publication | 31st International Symposium on Algorithms and Computation, ISAAC 2020 |
Editors | Yixin Cao, Siu-Wing Cheng, Minming Li |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 13:1-13:16 |
Number of pages | 16 |
ISBN (Electronic) | 9783959771733 |
DOIs | |
Publication status | Published - Dec 2020 |
Event | 31st International Symposium on Algorithms and Computation, ISAAC 2020 - Virtual, Hong Kong, China Duration: 14 Dec 2020 → 18 Dec 2020 |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 181 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 31st International Symposium on Algorithms and Computation, ISAAC 2020 |
---|---|
Country/Territory | China |
City | Virtual, Hong Kong |
Period | 14/12/20 → 18/12/20 |
Bibliographical note
Funding Information:Research on the topic of this paper was initiated at the 4th Workshop on Applied Geometric Algorithms (AGA 2018) in Langbroek, The Netherlands, supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208.
Publisher Copyright:
© Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen.
Funding
Research on the topic of this paper was initiated at the 4th Workshop on Applied Geometric Algorithms (AGA 2018) in Langbroek, The Netherlands, supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208.
Keywords
- Computational geometry
- Hausdorff distance
- Shape interpolation