Between Shapes, Using the Hausdorff Distance

M.J. van Kreveld, T. Miltzow, Tim Ophelders, Willem Sonke, Jordi L. Vermeulen

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


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 GmbH
ISBN (Print)978-3-95977-173-3
Publication statusPublished - 2020

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISSN (Print)1868-8969


  • computational geometry
  • Hausdorff distance
  • shape interpolation


Dive into the research topics of 'Between Shapes, Using the Hausdorff Distance'. Together they form a unique fingerprint.

Cite this