Matching Points with Things

被引：2

作者：

Aloupis, Greg ^{[1
]}

Cardinal, Jean ^{[1
]}

Collette, Sebastien ^{[1
]}

Demaine, Erik D. ^{[2
]}

Demaine, Martin L. ^{[2
]}

Dulieu, Muriel ^{[3
]}

Fabila-Monroy, Ruy ^{[4
]}

Hart, Vi ^{[5
]}

Hurtado, Ferran ^{[6
]}

Langerman, Stefan ^{[1
]}

Saumell, Maria ^{[6
]}

Seara, Carlos ^{[6
]}

Taslakian, Perouz ^{[1
]}

机构：

[1] Univ Libre Bruxelles, CP212 Bld Triomphe, B-1050 Brussels, Belgium

[2] MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA

[3] NYU, Polytech Inst, New York, NY 10003 USA

[4] Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City 04510, DF, Mexico

[5] SUNY Stony Brook, Stony Brook, NY 11794 USA

[6] Univ Politecn Cataluna, E-08034 Barcelona, Spain

来源：

LATIN 2010: THEORETICAL INFORMATICS | 2010年 / 6034卷

关键词：

EARTH MOVERS DISTANCE; GEOMETRY; PLANE; SETS;

D O I：

10.1007/978-3-642-12200-2_40

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point-object pairs. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their number is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a. convex polygon or are all on a. line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.

引用

页码：456 / +

页数：3

共 27 条

[1] SELECTING DISTANCES IN THE PLANE [J].

AGARWAL, PK ;

ARONOV, B ;

SHARIR, M ;

SURI, S .

ALGORITHMICA, 1993, 9 (05) :495-514

[2]

Aichholzer O., 2008, P 24 EUR C COMP GEOM, P119

[3] Compatible geometric matchings [J].

Aichholzer, Oswin ;

Bereg, Sergey ;

Dumitrescu, Adrian ;

Garcia, Alfredo ;

Huemer, Clemens ;

Hurtado, Ferran ;

Kano, Mikio ;

Marquez, Alberto ;

Rappaport, David ;

Smorodinsky, Shakhar ;

Souvaine, Diane ;

Urrutia, Jorge ;

Wood, David R. .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2009, 42 (6-7) :617-626

[4]

Alt Helmut., 1999, HDB COMPUTATIONAL GE, P121

[5]

[Anonymous], STOC 88

[6]

[Anonymous], LNCS

[7]

ARKIN EM, 1991, PROCEEDINGS OF THE SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P42

[8]

BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432

[9] Matching point sets with respect to the Earth Mover's Distance [J].

Cabello, Sergio ;

Giannopoulos, Panos ;

Knauer, Christian ;

Rote, Gunter .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2008, 39 (02) :118-133

[10] Pattern matching for spatial point sets [J].

Cardoze, DE ;

Schulman, LJ .

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :156-165

← 1 2 3 →