Between shapes, using the Hausdorff distance

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

doi:10.1016/j.comgeo.2021.101817

Between shapes, using the Hausdorff distance

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

Research output: Contribution to journal › Article › Academic › peer-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 that our result can be generalized to give an interpolated shape between A and B for any interpolation variable α between 0 and 1, and prove that the resulting morph has a bounded rate of change with respect to α. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.

Original language	English
Article number	101817
Pages (from-to)	1-14
Journal	Computational geometry
Volume	100
DOIs	https://doi.org/10.1016/j.comgeo.2021.101817
Publication status	Published - Jan 2022

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 . The second author is supported by the NWO under project no. 016.Veni.192.250 . The first and fifth authors are supported by the NWO TOP grant no. 612.001.651 .

Publisher Copyright:
© 2021 The Authors

Keywords

Computational geometry
Hausdorff distance
Morphing
Shape interpolation

Access to Document

10.1016/j.comgeo.2021.101817Licence: CC BY

1-s2.0-S0925772121000730-mainFinal published version, 873 KBLicence: CC BY

Cite this

@article{d99bcb4262254b7cb6a2297d71308c05,

title = "Between shapes, using the Hausdorff distance",

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 that our result can be generalized to give an interpolated shape between A and B for any interpolation variable α between 0 and 1, and prove that the resulting morph has a bounded rate of change with respect to α. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.",

keywords = "Computational geometry, Hausdorff distance, Morphing, Shape interpolation",

author = "Kreveld, \{Marc van\} and Tillmann Miltzow and Tim Ophelders and Willem Sonke and Vermeulen, \{Jordi L.\}",

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 . The second author is supported by the NWO under project no. 016.Veni.192.250 . The first and fifth authors are supported by the NWO TOP grant no. 612.001.651 . Publisher Copyright: {\textcopyright} 2021 The Authors",

year = "2022",

month = jan,

doi = "10.1016/j.comgeo.2021.101817",

language = "English",

volume = "100",

pages = "1--14",

journal = "Computational geometry",

issn = "0925-7721",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Between shapes, using the Hausdorff distance

AU - Kreveld, Marc van

AU - Miltzow, Tillmann

AU - Ophelders, Tim

AU - Sonke, Willem

AU - Vermeulen, Jordi L.

N1 - 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 . The second author is supported by the NWO under project no. 016.Veni.192.250 . The first and fifth authors are supported by the NWO TOP grant no. 612.001.651 . Publisher Copyright: © 2021 The Authors

PY - 2022/1

Y1 - 2022/1

N2 - 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 that our result can be generalized to give an interpolated shape between A and B for any interpolation variable α between 0 and 1, and prove that the resulting morph has a bounded rate of change with respect to α. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.

AB - 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 that our result can be generalized to give an interpolated shape between A and B for any interpolation variable α between 0 and 1, and prove that the resulting morph has a bounded rate of change with respect to α. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.

KW - Computational geometry

KW - Hausdorff distance

KW - Morphing

KW - Shape interpolation

UR - https://www.scopus.com/pages/publications/85111897307

U2 - 10.1016/j.comgeo.2021.101817

DO - 10.1016/j.comgeo.2021.101817

M3 - Article

SN - 0925-7721

VL - 100

SP - 1

EP - 14

JO - Computational geometry

JF - Computational geometry

M1 - 101817

ER -

Between shapes, using the Hausdorff distance

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this