Realistic Input Models for Geometric Algorithms |
| |
Authors: | de Berg van der Stappen Vleugels Katz |
| |
Affiliation: | (1) Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands., NL;(2) Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel., IL |
| |
Abstract: | Abstract. 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. |
| |
Keywords: | . Computational geometry Analysis of algorithms Input models. |
本文献已被 SpringerLink 等数据库收录! |
|