Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains

In English

Författare

Summary, in English

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.

Avdelning/ar

  • Computer Science

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

Ämne

  • Computer Science

Nyckelord

  • 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

Conference name

8th Scandinavian Workshop on Algorithm Theory.

Conference date

2002-07-03 - 2002-07-05

Conference place

Turku, Finland

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0302-9743
  • ISSN: 1611-3349