Advanced

Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains

Levcopoulos, Christos LU ; Lingas, Andrzej LU and Mitchell, Joseph S. B. (2002) 8th Scandinavian Workshop on Algorithm Theory. In Algorithm Theory - SWAT 2002 / Lecture Notes in Computer Science 2368. p.80-89
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
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
in
Algorithm Theory - SWAT 2002 / Lecture Notes in Computer Science
volume
2368
pages
80 - 89
publisher
Springer
conference name
8th Scandinavian Workshop on Algorithm Theory.
external identifiers
  • wos:000180068200009
  • scopus:84943273327
ISSN
0302-9743
1611-3349
DOI
10.1007/3-540-45471-3_9
language
English
LU publication?
yes
id
c3a88b97-0c8e-4d7e-837c-ca1d25d4b7cf (old id 321170)
date added to LUP
2007-11-28 09:26:40
date last changed
2017-06-11 03:45:27
@inproceedings{c3a88b97-0c8e-4d7e-837c-ca1d25d4b7cf,
  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.},
  author       = {Levcopoulos, Christos and Lingas, Andrzej and Mitchell, Joseph S. B.},
  booktitle    = {Algorithm Theory - SWAT 2002 / Lecture Notes in Computer Science},
  issn         = {0302-9743},
  keyword      = {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},
  language     = {eng},
  pages        = {80--89},
  publisher    = {Springer},
  title        = {Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains},
  url          = {http://dx.doi.org/10.1007/3-540-45471-3_9},
  volume       = {2368},
  year         = {2002},
}