Search

We study the problem of finding a polygonal chain of line segments to cover a set of points in ℝd, d≥2, with the goal of minimizing the number of links or turns in the chain. A chain of line segments that covers all points in the given set is called a covering tour if the chain is closed, and is called a covering path if the chain is open. A covering tour or a covering path is rectilinear if all segments in the chain are axis-parallel. We prove that the two problems Minimum-Link Rectilinear Covering Tour and Minimum-Link Rectilinear Covering Path are both NP-hard in ℝ10.

The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n log n) or output sensitive O(n log h) time, where n is the number of line-segments and h is the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n log h) time. Our algorithms are given in the Euclidean plane but they hold also in the general Lp metric, 1 ≤ p ≤ ∞.

A curvature-based algorithm to simplify a polygonal curve is described, together with its implementation. The so-called SimpliPoly algorithm uses Bézier curves to approximate pieces of the input curve, and assign curvature estimates to vertices of the input polyline from curvature values computed for the Bézier approximations. The authors' implementation of SimpliPoly is interactive and available freely on-line. Additionally, a third-party implementation of SimpliPoly as a plug-in for the GNU Blender 3D modeling software is available. Empirical comparisons indicate that SimpliPoly performs as well as the widely-used Douglas-Peucker algorithm in most situations, and significantly better, because it is curvature-driven, in applications where it is necessary to preserve local features.

Given an n-vertex polygonal curve P = [p1, p2, …, pn] in the 2-dimensional space R2, we consider the problem of approximating P by finding another polygonal curve [Formula: see text] such that the vertex sequence of P′ is an ordered subsequence of the vertices along P. The goal is to either minimize the size m of P′ for a given error tolerance ∊ (called the min-# problem), or minimize the deviation error ∊ between P and P′ for a given size m of P′ (called the min-∊ problem). We present useful techniques and develop efficient algorithms for solving the 2-D min-# and min-∊ problems under two commonly-used error criteria for curve approximations. Our algorithms improve substantially the space bounds of the previously best known results on the same problems while maintain the same time bounds as those of the best known algorithms. We further show that our 2-D techniques can be used to improve the time and space bounds for a special case of the 3-D min-# and min-∊ problems.

Let [Formula: see text] be a given nonempty family of directions in the plane. For a multiply connected polygonal domain P with polygonal holes, possibly degenerate, we determine the minimum number of convex polygons into which P is partitioned by linear cuts in the directions from [Formula: see text].

We improve the time complexities for solving the polygonal curve approximation problems formulated by Imai and Iri. The time complexity for approximating any polygonal curve of n vertices with minimum number of line segments can be improved from O(n2 log n) to O(n2). The time complexity for approximating any polygonal curve with minimum error can also be improved from O(n2 log 2n) to O(n2 log n). We further show that if the curve to be approximated forms part of a convex polygon, the two problems can be solved in O(n) and O(n2) time respectively for both open and closed polygonal curves.

We study several variations on one basic approach to the task of simplifying a plane polygon or subdivision: Fatten the given object and construct an approximation inside the fattened region. We investigate fattening by convolving the segments or vertices with disks and attempt to approximate objects with the minimum number of line segments, or with near the minimum, by using efficient greedy algorithms. We give some variants that have linear or O(n log n) algorithms approximating polygonal chains of n segments. We also show that approximating subdivisions and approximating with chains with. no self-intersections are NP-hard.