LIPIcs.SoCG.2016.63.pdf
- Filesize: 495 kB
- 15 pages
Document
Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties
Authors
-
Part of:
Volume:
32nd International Symposium on Computational Geometry (SoCG 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-10
Cite As Get BibTex
Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson. Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.63
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) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively.
Subject Classification
Keywords
- shape matching
- convexity
- symmetric difference
- homotheties
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
H.-K. Ahn, S.-W. Cheng, and I. Reinbacher. Maximum overlap of convex polytopes under translation. Computational Geometry: Theory and Applications, 46:552-565, 2013.
-
H. Alt, J. Blömer, M. Godau, and H. Wagener. Approximation of convex polygons. In Automata, Languages and Programming, volume 443 of LNCS, pages 703-716. Springer, 1990.
-
H. Alt, U. Fuchs, G. Rote, and G. Weber. Matching convex shapes with respect to the symmetric difference. Algorithmica, 21:89-103, 1998.
-
D. Avis, P. Bose, T. Shermer, J. Snoeyink, G. Toussaint, and B. Zhu. On the sectional area of convex polytopes. In Communication at the 12th Annual Symposium on Computational Geometry, page C, 1996.
-
P. Brass and M. Lassak. Problems on approximation by triangles. Geombinatorics, 10:103-115, 2001.
-
B. Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete &Computational Geometry, 9:145-158, 1993.
-
M. de Berg, O. Cheong, O. Devillers, M. van Kreveld, and M. Teillaud. Computing the maximum overlap of two convex polygons under translations. Theory of Computing Systems, 31:613-628, 1998.
-
R. Fleischer, K. Mehlhorn, G. Rote, E. Welzl, and C. Yap. Simultaneous inner and outer approximation of shapes. Algorithmica, 8:365-389, 1992.
-
G. N. Frederickson and D. B. Johnson. Generalized selection and ranking: sorted matrices. SIAM Journal on Computing, 13:14-30, 1984.
-
H. Groemer. On the symmetric difference metric for convex bodies. Beiträge zur Algebra und Geometrie, 41:107-114, 2000.
-
J. Matoušek. Randomized optimal algorithm for slope selection. Information Processing Letters, 39:183-187, 1991.
-
N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of ACM, 30:852-865, 1983.
-
R. Schneider. Convex Bodies - the Brunn-Minkowski theory. Cambridge University Press, 1993.
-
D. Schymura. An upper bound on the volume of the symmetric difference of a body and a congruent copy. Advances in Geometry, 14:287-298, 2014.
-
D. M. J. Tax and R. P. W. Duin. Support vector data description. Machine Learning, 54:45-66, 2004.
-
R. Veltkamp and M. Hagedoorn. Shape similarity measures, properties and constructions. In Advances in Visual Information Systems, volume 1929 of LNCS, pages 467-476. Springer, 2000.