Efficient randomized algorithms for some geometric optimization problems

被引:55
作者
Agarwal, PK
Sharir, M
机构
[1] TEL AVIV UNIV, SCH MATH SCI, IL-69978 TEL AVIV, ISRAEL
[2] NYU, COURANT INST MATH SCI, NEW YORK, NY 10012 USA
关键词
D O I
10.1007/BF02712871
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper we first prove the following combinatorial bound, concerning the complexity of the vertical decomposition of the minimization diagram of trivariate functions: Let F be a collection of n totally or partially defined algebraic trivariate functions of constant maximum degree, with the additional property that, for a given pair of functions f, f' epsilon F, the surface f(x, y, z) = f'(x: y, z) is xy-monotone (actually, we need a somewhat weaker property). We show that the vertical decomposition of the minimization diagram of F consists of O (n(3+epsilon)) cells (each of constant description complexity), for any epsilon > 0. In the second part of the paper, we present a general technique that yields faster randomized algorithms for solving a number of geometric optimization problems, including (i) computing the width of a point set in 3-space, (ii) computing the minimum-width annulus enclosing a set of n points in the plane, and (iii) computing the ''biggest stick'' inside a simple polygon in the plane. Using the above result on vertical decompositions, we show that the expected running time of all three algorithms is O (n(3/2+epsilon)), for epsilon > 0. Our algorithm improves and simplifies previous solutions of all three problems.
引用
收藏
页码:317 / 337
页数:21
相关论文
共 35 条
[1]  
AGARWAL, 1995, P 11 ANN S COMP GEOM, P182
[2]  
Agarwal P. K., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P348, DOI 10.1145/177424.178081
[3]   APPLICATIONS OF PARAMETRIC SEARCHING IN GEOMETRIC OPTIMIZATION [J].
AGARWAL, PK ;
SHARIR, M ;
TOLEDO, S .
JOURNAL OF ALGORITHMS, 1994, 17 (03) :292-318
[4]   COMPUTING THE LONGEST DIAGONAL OF A SIMPLE POLYGON [J].
AGGARWAL, A ;
SURI, S .
INFORMATION PROCESSING LETTERS, 1990, 35 (01) :13-18
[5]   DIAMETER, WIDTH, CLOSEST LINE PAIR, AND PARAMETRIC SEARCHING [J].
CHAZELLE, B ;
EDELSBRUNNER, H ;
GUIBAS, L ;
SHARIR, M .
DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 10 (02) :183-196
[6]   AN ALGORITHM FOR GENERALIZED POINT LOCATION AND ITS APPLICATIONS [J].
CHAZELLE, B ;
SHARIR, M .
JOURNAL OF SYMBOLIC COMPUTATION, 1990, 10 (3-4) :281-309
[7]   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
[8]  
CHAZELLE B, 1989, LECT NOTES COMPUT SC, V372, P179
[9]  
CHAZELLE B, 1993, ADV COMPUTING RES, V1, P1
[10]   COMBINATORIAL COMPLEXITY-BOUNDS FOR ARRANGEMENTS OF CURVES AND SPHERES [J].
CLARKSON, KL ;
EDELSBRUNNER, H ;
GUIBAS, LJ ;
SHARIR, M ;
WELZL, E .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) :99-160