Search

We study the shortest k -violation path problem in a simple polygon. Let P be a simple polygon in ℝ 2 with n vertices and let s , t be a pair of points in P. Let i n t (P) represent the interior of P. Let P ̃ = ℝ 2 \ i n t (P) represent the exterior of P. For an integer k ≥ 0 , the shortest k -violation path problem in P is the problem of computing the shortest path from s to t in P , such that at most k path segments are allowed to be in P ̃. The subpaths of a k -violation path are not allowed to bend in P ̃. For any k , we present a (1 + 2 𝜖) factor approximation algorithm for the problem that runs in O (n 2 σ 2 k log n 2 σ 2 + n 2 σ 2 k) time. Here σ = O (log δ (L r)) and δ , L , r are geometric parameters. [ABSTRACT FROM AUTHOR]

A greedily routable region (GRR) is a closed subset of , in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected. [ABSTRACT FROM AUTHOR]

We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n – k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divide-and-conquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation. [ABSTRACT FROM AUTHOR]

We generalize the operation of flipping an edge in a triangulation to that of flipping several edges simultaneously. Our main result is an optimal upper bound on the number of simultaneous flips that are needed to transform a triangulation into another. Our results hold for triangulations of point sets and for polygons. [ABSTRACT FROM AUTHOR]

We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types: (1) the elements form the cells of a Voronoï diagram, (2) all elements have two opposite 90° angles, (3) all elements are kites, or (4) all angles are at most 120°. In each case the total number of elements is O(n), where n is the number of input vertices. [ABSTRACT FROM AUTHOR]

Assume that an isomorphism between two n-vertex simple polygons, P,Q (with k,l reflex vertices, respectively) is given. We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of P and Q, respectively. The first algorithm computes isomorphic triangulations of P and Q by introducing at most O((k+l)[sup 2]) Steiner points and has running time O(n+(k+l)[sup 2]). The second algorithm computes isomorphic traingulations of P and Q by introducing at most O(kl) Steiner points and has running time O(n+kllog n). The number of Steiner points introduced by the second algorithm is also worst-case optimal. Unlike the O(n[sup 2]) algorithm of Aronov, Seidel and Souvaine[sup 1] our algorithms are sensitive to the number of reflex vertices of the polygons. In particular, our algorithms have linear running time when k+l≤√n for the first algorithm, and kl≤n/log n for the second algorithm. [ABSTRACT FROM AUTHOR]

We give a result that implies an improvement by a factor of log log n in the hypercube bounds for the geometric problems of batched planar point location, trapezoidal decomposition, and polygon triangulation. The improvements are achieved through a better solution to the multisearch problem on a hypercube, a parallel search problem where the elements in the data structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. Whereas the previous best solution to this problem took O(log n(log log n)[sup 3]) time on an n-processor hypercube, the solution given here takes O(log n(log log n)[sup 2]) time on an n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID. [ABSTRACT FROM AUTHOR]