Approximating convex shapes with respect to symmetric difference under homotheties

Juyoung Yon, Sang Bae Won, Siu Wing Cheng, Otfried Cheong, Bryan T. Wilkinson

    Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

    95 Downloads (Pure)

    Abstract

    The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m + n)log3(m + n)) expected time, where n and m denote the number of vertices of P and C, respectively.

    Original languageEnglish
    Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
    EditorsSándor Fekete, Anna Lubiw
    Number of pages15
    Volume51
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    Publication date2016
    Pages63.1-63.15
    ISBN (Electronic)9783959770095
    DOIs
    Publication statusPublished - 2016
    Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
    Duration: 14 Jun 201617 Jun 2016

    Conference

    Conference32nd International Symposium on Computational Geometry, SoCG 2016
    Country/TerritoryUnited States
    CityBoston
    Period14/06/201617/06/2016
    SeriesLeibniz International Proceedings in Informatics
    Volume51
    ISSN1868-8969

    Keywords

    • Convexity
    • Homotheties
    • Shape matching
    • Symmetric difference

    Fingerprint

    Dive into the research topics of 'Approximating convex shapes with respect to symmetric difference under homotheties'. Together they form a unique fingerprint.

    Cite this