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 Ω(n log(x + 2)) in the algebraic decision tree model. We also prove a lower bound of Ω(n log(k/n)) for k > n in the algebraic decision tree model; since x ≤ k, the upper bound of O(n log(k + 2)) follows. We also show that a polygonal chain with k proper intersections can adding at most 2k new vertices in time O(n·min{k~(1/2), log n} + k). This yields O(n·min{k~(1/2), 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.
展开▼
