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

被引：166
作者：
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 [J].
BRUCKER, P ;
MEYER, W .
DISCRETE APPLIED MATHEMATICS, 1988, 20 (02) :91-100
[2]   CYCLIC SCHEDULES FOR R-IRREGULARLY OCCURRING EVENTS [J].
BRUCKER, P ;
BURKARD, RE ;
HURINK, J .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1990, 30 (02) :173-189
[3]   OPTIMAL SCHEDULES FOR PERIODICALLY RECURRING EVENTS [J].
BURKARD, RE .
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 [J].
Lee, D. T. ;
Wu, Y. F. .
ALGORITHMICA, 1986, 1 (1-4) :193-211
[6]  
Preparata F. P., 2012, COMPUTATIONAL GEOMET
[7]   OBTAINING LOWER BOUNDS USING ARTIFICIAL COMPONENTS [J].
RAMANAN, P .
INFORMATION PROCESSING LETTERS, 1987, 24 (04) :243-246
[8]  
[No title captured]
1