Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains

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

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingForskningPeer review

    5 Citeringar (SciVal)

    Sammanfattning

    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.
    Originalspråkengelska
    Titel på gästpublikationAlgorithm Theory - SWAT 2002 / Lecture Notes in Computer Science
    FörlagSpringer
    Sidor80-89
    Volym2368
    DOI
    StatusPublished - 2002
    Evenemang8th Scandinavian Workshop on Algorithm Theory. - Turku, Finland
    Varaktighet: 2002 jul 32002 jul 5

    Publikationsserier

    Namn
    Volym2368
    ISSN (tryckt)0302-9743
    ISSN (elektroniskt)1611-3349

    Konferens

    Konferens8th Scandinavian Workshop on Algorithm Theory.
    Land/TerritoriumFinland
    OrtTurku
    Period2002/07/032002/07/05

    Ämnesklassifikation (UKÄ)

    • Datavetenskap (datalogi)

    Fingeravtryck

    Utforska forskningsämnen för ”Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains”. Tillsammans bildar de ett unikt fingeravtryck.

    Citera det här