COMPUTING THE MINIMUM HAUSDORFF DISTANCE BETWEEN 2 POINT SETS ON A LINE UNDER TRANSLATION

被引：162

作者：

ROTE, G

机构：

[1] Institut für Mathematik, Technische Universität Graz, A-8010 Graz

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 38卷 / 03期

关键词：

COMPUTATIONAL GEOMETRY; HAUSDORFF DISTANCE; PATTERN RECOGNITION; PATTERN MATCHING;

D O I：

10.1016/0020-0190(91)90233-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given two sets of points on a line, we want to translate one of them so that their Hausdorff distance (the maximum of the distances from a point in any of the sets to the nearest point in the other set) is as small as possible. We present an optimal O(n log n) algorithm for this problem.

引用

页码：123 / 127

页数：5

共 8 条

[1] SCHEDULING 2 IRREGULAR POLYGONS
BRUCKER, P
MEYER, W
[J]. DISCRETE APPLIED MATHEMATICS, 1988, 20 (02) : 91 - 100
[2] CYCLIC SCHEDULES FOR R-IRREGULARLY OCCURRING EVENTS
BRUCKER, P
BURKARD, RE
HURINK, J
[J]. JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1990, 30 (02) : 173 - 189
[3] OPTIMAL SCHEDULES FOR PERIODICALLY RECURRING EVENTS
BURKARD, RE
[J]. DISCRETE APPLIED MATHEMATICS, 1986, 15 (2-3) : 167 - 180
[4] HUTTENLOCHER DP, 1990, 6TH P ACM S COMP GEO, P340
[5] Geometric Complexity of Some Location Problems
Lee, D. T.
Wu, Y. F.
[J]. ALGORITHMICA, 1986, 1 (1-4) : 193 - 211
[6] Preparata F. P., 2012, COMPUTATIONAL GEOMET
[7] OBTAINING LOWER BOUNDS USING ARTIFICIAL COMPONENTS
RAMANAN, P
[J]. INFORMATION PROCESSING LETTERS, 1987, 24 (04) : 243 - 246
[8] [No title captured]

← 1 →