Realistic input models for geometric algorithms

M. Berg, de, A.F. van der Stappen, J.M. Vleugels, M.J. Katz

    Research output: Contribution to journalArticleAcademicpeer-review

    73 Citations (Scopus)

    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.
    Original languageEnglish
    Pages (from-to)81-97
    JournalAlgorithmica
    Volume34
    Issue number1
    DOIs
    Publication statusPublished - 2002

    Fingerprint

    Geometric Algorithms
    Model
    Worst-case Analysis
    Geographic Information Systems
    Geographic information systems
    Irregular
    Verify
    Predict
    Scenarios
    Experimental Results

    Cite this

    Berg, de, M., van der Stappen, A. F., Vleugels, J. M., & Katz, M. J. (2002). Realistic input models for geometric algorithms. Algorithmica, 34(1), 81-97. https://doi.org/10.1007/s00453-002-0961-x
    Berg, de, M. ; van der Stappen, A.F. ; Vleugels, J.M. ; Katz, M.J. / Realistic input models for geometric algorithms. In: Algorithmica. 2002 ; Vol. 34, No. 1. pp. 81-97.
    @article{23ae008f778c40ae9aedbc11edfe9544,
    title = "Realistic input models for geometric algorithms",
    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.",
    author = "{Berg, de}, M. and {van der Stappen}, A.F. and J.M. Vleugels and M.J. Katz",
    year = "2002",
    doi = "10.1007/s00453-002-0961-x",
    language = "English",
    volume = "34",
    pages = "81--97",
    journal = "Algorithmica",
    issn = "0178-4617",
    publisher = "Springer",
    number = "1",

    }

    Berg, de, M, van der Stappen, AF, Vleugels, JM & Katz, MJ 2002, 'Realistic input models for geometric algorithms', Algorithmica, vol. 34, no. 1, pp. 81-97. https://doi.org/10.1007/s00453-002-0961-x

    Realistic input models for geometric algorithms. / Berg, de, M.; van der Stappen, A.F.; Vleugels, J.M.; Katz, M.J.

    In: Algorithmica, Vol. 34, No. 1, 2002, p. 81-97.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Realistic input models for geometric algorithms

    AU - Berg, de, M.

    AU - van der Stappen, A.F.

    AU - Vleugels, J.M.

    AU - Katz, M.J.

    PY - 2002

    Y1 - 2002

    N2 - 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.

    AB - 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.

    U2 - 10.1007/s00453-002-0961-x

    DO - 10.1007/s00453-002-0961-x

    M3 - Article

    VL - 34

    SP - 81

    EP - 97

    JO - Algorithmica

    JF - Algorithmica

    SN - 0178-4617

    IS - 1

    ER -