Matching convex shapes with respect to the symmetric difference

被引：25

作者：

Alt, H

Fuchs, U

Rote, G

Weber, G

机构：

[1] Free Univ Berlin, Inst Informat, D-14195 Berlin, Germany

[2] Graz Tech Univ, Inst Math, A-8010 Graz, Austria

来源：

ALGORITHMICA | 1998年 / 21卷 / 01期

关键词：

computational geometry; convex geometry; shape matching; centroid;

D O I：

10.1007/PL00009210

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 optimum. This leads to efficient approximate matching algorithms for convex figures.

引用

页码：89 / 103

页数：15

共 13 条

[1] APPLICATIONS OF PARAMETRIC SEARCHING IN GEOMETRIC OPTIMIZATION [J].

AGARWAL, PK ;

SHARIR, M ;

TOLEDO, S .

JOURNAL OF ALGORITHMS, 1994, 17 (03) :292-318

[2] Matching shapes with a reference point [J].

Aichholzer, O ;

Alt, H ;

Rote, G .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1997, 7 (04) :349-363

[3]

ALT H, 1990, LECT NOTES COMPUT SC, V443, P703

[4]

ALT H, 1991, P 7 ANN S COMP GEOM, P186

[5]

ALT H, 1996, LNCS, V1136, P320

[6]

[Anonymous], 1983, Convexity and Its Applications, DOI DOI 10.1007/978-3-0348-5858-8_7

[7]

[Anonymous], 1993, HDB CONVEX GEOMETRY

[8]

Avis D., 1996, Proceedings of the Twelfth Annual Symposium on Computational Geometry, FCRC '96, pC11

[9]

BONNESEN T, 1933, ERGEBNISSE MATH GREN, V3

[10]

CHEW LP, 1993, P 5 CAN C COMP GEOM, P151

← 1 2 →