Realistic input models for geometric algorithms

被引:66
作者
de Berg, M
Katz, MJ
van der Stappen, AF
Vleugels, J
机构
[1] Univ Utrecht, Inst Informat & Comp Sci, NL-3508 TB Utrecht, Netherlands
[2] Ben Gurion Univ Negev, Dept Math & Comp Sci, IL-84105 Beer Sheva, Israel
关键词
computational geometry; analysis of algorithms; input models;
D O I
10.1007/s00453-002-0961-x
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The traditional worst-case analysis often fails to predict the actual behavior of the running time of geometric algorithms in practical situations. One reason is that worst-case scenarios are often very contrived and do not occur in practice. To avoid this, models are needed that describe the properties that realistic inputs have, so that the analysis can take these properties into account. We try to bring some structure to this emerging research direction. In particular, we present the following results: We show the relations between various models that have been proposed in the literature. For several of these models, we give algorithms to compute the model parameter(s) for a given (planar) scene; these algorithms can be used to verify whether a model is appropriate for typical scenes in some application area. As a case study, we give some experimental results on the appropriateness of some of the models for one particular type of scene often encountered in geographic information systems, namely certain triangulated irregular networks.
引用
收藏
页码:81 / 97
页数:17
相关论文
共 29 条
[1]   COMPUTING DEPTH ORDERS FOR FAT OBJECTS AND RELATED PROBLEMS [J].
AGARWAL, PK ;
KATZ, MJ ;
SHARIR, M .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1995, 5 (04) :187-206
[2]   Binary space partitions for fat rectangles [J].
Agarwal, PK ;
Grove, EF ;
Murali, TM ;
Vitter, JS .
37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :482-491
[3]   APPROXIMATE MOTION PLANNING AND THE COMPLEXITY OF THE BOUNDARY OF THE UNION OF SIMPLE GEOMETRIC-FIGURES [J].
ALT, H ;
FLEISCHER, R ;
KAUFMANN, M ;
MEHLHORN, K ;
NAHER, S ;
SCHIRRA, S ;
UHRIG, C .
ALGORITHMICA, 1992, 8 (5-6) :391-406
[4]  
Banon J. M., 1990, Proceedings 1990 IEEE International Conference on Robotics and Automation (Cat. No.90CH2876-1), P1548, DOI 10.1109/ROBOT.1990.126228
[5]   PROVABLY GOOD MESH GENERATION [J].
BERN, M ;
EPPSTEIN, D ;
GILBERT, J .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (03) :384-409
[6]   Dynamic motion planning in low obstacle density environments [J].
Berretty, RP ;
Overmars, MH ;
van der Stappen, AF .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 11 (3-4) :157-173
[7]  
CHEN Z, 1988, P 8 INT S COMP ASS C, P50
[8]  
de Berg M, 1998, LECT NOTES COMPUT SC, V1432, P83, DOI 10.1007/BFb0054357
[9]   Linear size binary space partitions for uncluttered scenes [J].
de Berg, M .
ALGORITHMICA, 2000, 28 (03) :353-366
[10]  
De Berg M., 2000, COMPUTATIONAL GEOMET, DOI DOI 10.1007/978-3-662-03427-9