Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains

Christos Levcopoulos, Andrzej Lingas, Joseph S. B. Mitchell

    Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingResearchpeer-review

    5 Citations (SciVal)

    Abstract

    We study some fundamental computational geometry problems with the goal to exploit structure in input data that is given as a sequence C = (p(1), p(2), . . . ,p(n)) of points that are "almost sorted" in the sense that the polygonal chain they define has a possibly small number, k, of self-intersections, or the chain can be partitioned into a small number, X, of simple subchains. We give results that show adaptive complexity in terms of k or X: when k or X is small compared to n, we achieve time bounds that approach the linear-time (O(n)) bounds known for the corresponding problems on simple polygonal chains. In particular, we show that the convex hull of C can be computed in O(n log(X + 2)) time, and prove a matching lower bound of Omega(n log(X + 2)) in the algebraic decision tree model. We also prove a lower bound of Omega(n log(k/n)) for k > n in the algebraic decision tree model; since X less than or equal to k, the upper bound of O(n log(k + 2)) follows. We also show that a polygonal chain with k proper inter sections can be transformed into a polygonal chain without proper intersections by adding at most 2k new vertices in time O(n (.) min{rootk, log n} + k). This yields O(n (.) min{rootk, log n} + k)-time algorithms for triangulation, in particular the constrained Delaunay triangulation of a polygonal chain where the proper intersection points are also regarded as vertices.
    Original languageEnglish
    Title of host publicationAlgorithm Theory - SWAT 2002 / Lecture Notes in Computer Science
    PublisherSpringer
    Pages80-89
    Volume2368
    DOIs
    Publication statusPublished - 2002
    Event8th Scandinavian Workshop on Algorithm Theory. - Turku, Finland
    Duration: 2002 Jul 32002 Jul 5

    Publication series

    Name
    Volume2368
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference8th Scandinavian Workshop on Algorithm Theory.
    Country/TerritoryFinland
    CityTurku
    Period2002/07/032002/07/05

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • upper bound
    • lower bound
    • algebraic decision tree model
    • polygonal chains
    • constrained Delaunay triangulation
    • adaptive complexity
    • triangulations of polygonal chains
    • polygonal chain
    • computational geometry
    • adaptive algorithms
    • convex hulls

    Fingerprint

    Dive into the research topics of 'Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains'. Together they form a unique fingerprint.

    Cite this