Realistic input models for geometric algorithms
Mark de Berg, Matthew Katz, A. Frank van der Stappen, Jules Vleugels · 1997
Many algorithms developed in computationid geometry are needlessly complicated and slow because they have to be prepared for very complicated, hypathetical inputs.To avoid this, realistic models are needed that describe the properties that realistic inputs have, so that algorithms can de designed that take advantage of these properties.This can lead to algorithms that are provably efficient in realktic situations.We obtain some fundamental results in this research direction.In particular, we have the following results.. We show the relations between various models that have been proposed in the literature.q For several of these models, we give algorithms to compute the model parameter(s) for a given scene; these algorithms can be used to verify whether a model is appropriate for typical scenesin some application area.q As a case study, we give some experimental results on the appropriateness of some of the models for one particular type of scenes often encountered in GIS, namely certain triangulated irregular networks.