Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains
(2002) 8th Scandinavian Workshop on Algorithm Theory. 2368. p.8089 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 selfintersections, 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 lineartime (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 selfintersections, 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 lineartime (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:
https://lup.lub.lu.se/record/321170
 author
 Levcopoulos, Christos ^{LU} ; Lingas, Andrzej ^{LU} and Mitchell, Joseph S. B.
 organization
 publishing date
 2002
 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
 host publication
 Algorithm Theory  SWAT 2002 / Lecture Notes in Computer Science
 volume
 2368
 pages
 80  89
 publisher
 Springer
 conference name
 8th Scandinavian Workshop on Algorithm Theory.
 conference location
 Turku, Finland
 conference dates
 20020703  20020705
 external identifiers

 wos:000180068200009
 scopus:84943273327
 ISSN
 16113349
 03029743
 DOI
 10.1007/3540454713_9
 language
 English
 LU publication?
 yes
 id
 c3a88b970c8e4d7e837cca1d25d4b7cf (old id 321170)
 date added to LUP
 20160401 12:10:21
 date last changed
 20210217 01:18:31
@inproceedings{c3a88b970c8e4d7e837cca1d25d4b7cf, 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 selfintersections, 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 lineartime (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 = {16113349}, language = {eng}, pages = {8089}, publisher = {Springer}, title = {Adaptive algorithms for constructing convex hulls and triangulations of polygonal chains}, url = {http://dx.doi.org/10.1007/3540454713_9}, doi = {10.1007/3540454713_9}, volume = {2368}, year = {2002}, }