Du är här

Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains

Publiceringsår: 2002
Språk: Engelska
Sidor: 80-89
Publikation/Tidskrift/Serie: Algorithm Theory - SWAT 2002 / Lecture Notes in Computer Science
Volym: 2368
Dokumenttyp: Konferensbidrag
Förlag: Springer

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.

Disputation

Nyckelord

  • Technology and Engineering
  • 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

Övrigt

8th Scandinavian Workshop on Algorithm Theory.
2002-07-03/2002-07-05
Turku, Finland
Published
Yes
  • ISSN: 0302-9743

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen

LERU logo U21 logo