MATCHING CONVEX SHAPES WITH RESPECT TO THE SYMMETRICAL DIFFERENCE

Authors
ALT H FUCHS U ROTE G WEBER G
Citation
H. Alt et al., MATCHING CONVEX SHAPES WITH RESPECT TO THE SYMMETRICAL DIFFERENCE, Algorithmica, 21(1), 1998, pp. 89-103
Citations number
13
Categorie Soggetti
Mathematics,"Computer Science Software Graphycs Programming",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
21
Issue
1
Year of publication
1998
Pages
89 - 103
Database
ISI
SICI code
0178-4617(1998)21:1<89:MCSWRT>2.0.ZU;2-C
Abstract
This paper deals with questions from convex geometry related to shape matching. In particular, we consider the problem of moving one convex figure over another, minimizing the area of their symmetric difference . We show that if we just let the two centers of gravity coincide, the resulting symmetric difference is within a factor of 11/3 of the opti mum. This leads to efficient approximate matching algorithms for conve x figures.