APPLICATIONS OF PARAMETRIC SEARCHING IN GEOMETRIC OPTIMIZATION

被引:83
作者
AGARWAL, PK
SHARIR, M
TOLEDO, S
机构
[1] TEL AVIV UNIV,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL
[2] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012
[3] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139
关键词
D O I
10.1006/jagm.1994.1038
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We present several applications in computational geometry of Megiddo's parametric searching technique. These applications include: (1) Finding the minimum Hausdorff distance in the Euclidean metric between two polygonal regions under translation; (2) Computing the biggest line segment that can be placed inside a simple polygon; (3) Computing the smallest width annulus that contains a given set of given points in the plane; (4) Given a set of n points in 3-space, finding the largest radius r such that if we place a ball of radius r around each point, no segment connecting a pair of points is intersected by a third ball. Besides obtaining efficient solutions to all these problems (which, in every case, either improve considerably previous solutions or are the first nontrivial solutions to these problems), our goal is to demonstrate the versatility of the parametric searching technique. (C) 1994 Academic Press, Inc.
引用
收藏
页码:292 / 318
页数:27
相关论文
共 45 条
[11]   VISIBILITY AND INTERSECTION PROBLEMS IN PLANE GEOMETRY [J].
CHAZELLE, B ;
GUIBAS, LJ .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) :551-581
[12]  
Chazelle B., 1982, 23rd Annual Symposium on Foundations of Computer Science, P339, DOI 10.1109/SFCS.1982.58
[13]   AN ALGORITHM FOR GENERALIZED POINT LOCATION AND ITS APPLICATIONS [J].
CHAZELLE, B ;
SHARIR, M .
JOURNAL OF SYMBOLIC COMPUTATION, 1990, 10 (3-4) :281-309
[14]   ALGORITHMS FOR BICHROMATIC LINE-SEGMENT PROBLEMS AND POLYHEDRAL TERRAINS [J].
CHAZELLE, B ;
EDELSBRUNNER, H ;
GUIBAS, LJ ;
SHARIR, M .
ALGORITHMICA, 1994, 11 (02) :116-132
[15]   TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME [J].
CHAZELLE, B .
DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :485-524
[16]   A SINGLY EXPONENTIAL STRATIFICATION SCHEME FOR REAL SEMIALGEBRAIC VARIETIES AND ITS APPLICATIONS [J].
CHAZELLE, B ;
EDELSBRUNNER, H ;
GUIBAS, LJ ;
SHARIR, M .
THEORETICAL COMPUTER SCIENCE, 1991, 84 (01) :77-105
[17]  
Chazelle B., 1983, ADV COMPUTING RES, VI, P1
[18]   APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2. [J].
CLARKSON, KL ;
SHOR, PW .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421
[19]   AN OPTIMAL-TIME ALGORITHM FOR SLOPE SELECTION [J].
COLE, R ;
SALOWE, JS ;
STEIGER, WL ;
SZEMEREDI, E .
SIAM JOURNAL ON COMPUTING, 1989, 18 (04) :792-810
[20]  
COLE R, 1984, J ASSOC COMPUT MACH, V31, P200