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.
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:
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
- 2002-07-03 - 2002-07-05
- 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
- 2016-04-01 12:10:21
- date last changed
- 2024-01-08 11:00:13
@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}},
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}},
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}},
doi = {{10.1007/3-540-45471-3_9}},
volume = {{2368}},
year = {{2002}},
}