Between shapes, using the Hausdorff distance

Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, Jordi L. Vermeulen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publication31st International Symposium on Algorithms and Computation, ISAAC 2020
EditorsYixin Cao, Siu-Wing Cheng, Minming Li
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages13:1-13:16
Number of pages16
ISBN (Electronic)9783959771733
DOIs
Publication statusPublished - Dec 2020
Event31st International Symposium on Algorithms and Computation, ISAAC 2020 - Virtual, Hong Kong, China
Duration: 14 Dec 202018 Dec 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume181
ISSN (Print)1868-8969

Conference

Conference31st International Symposium on Algorithms and Computation, ISAAC 2020
Country/TerritoryChina
CityVirtual, Hong Kong
Period14/12/2018/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

Fingerprint

Dive into the research topics of 'Between shapes, using the Hausdorff distance'. Together they form a unique fingerprint.

Cite this