Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing Nonsimple Polygons of Minimum Perimeter
275
0
0.0
(
0
)
Added by
Sandor P. Fekete
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of integer programming, an additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting additional geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.
rate research
Read More
A rectilinear polygon is a polygon whose edges are axis-aligned. Walking counterclockwise on the boundary of such a polygon yields a sequence of left turns and right turns. The number of left turns always equals the number of right turns plus 4. It is known that any such sequence can be realized by a rectilinear polygon. In this paper, we consider the problem of finding realizations that minimize the perimeter or the area of the polygon or the area of the bounding box of the polygon. We show that all three problems are NP-hard in general. This answers an open question of Patrignani [CGTA 2001], who showed that it is NP-hard to minimize the area of the bounding box of an orthogonal drawing of a given planar graph. We also show that realizing polylines with minimum bounding box area is NP-hard. Then we consider the special cases of $x$-monotone and $xy$-monotone rectilinear polygons. For these, we can optimize the three objectives efficiently.
We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the $1$-dimensional homology classes with $mathbb{Z}_2$ coefficients in a given simplicial complex $K$. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al., runs in $O(N^omega + N^2 g)$ time, where $N$ denotes the number of simplices in $K$, $g$ denotes the rank of the $1$-homology group of $K$, and $omega$ denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex $K$. The first algorithm runs in $tilde{O}(m^omega)$ time, where $m$ denotes the number of edges in $K$, whereas the second algorithm runs in $O(m^omega + N m^{omega-1})$ time. We also study the problem of finding a minimum cycle basis in an undirected graph $G$ with $n$ vertices and $m$ edges. The best known algorithm for this problem runs in $O(m^omega)$ time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in $tilde{O}(m^omega)$ time.
Given a set $S$ of $m$ point sites in a simple polygon $P$ of $n$ vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for $S$ in $P$. It is known that the problem has an $Omega(n+mlog m)$ time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in $O(n+mlog m)$ expected time. The previous best deterministic algorithms solve the problem in $O(nlog log n+ mlog m)$ time [Oh, Barba, and Ahn, SoCG 2016] or in $O(n+mlog m+mlog^2 n)$ time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of $O(n+mlog m)$ time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.
We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.
Given a set of $n$ terminals, which are points in $d$-dimensional Euclidean space, the minimum Manhattan network problem (MMN) asks for a minimum-length rectilinear network that connects each pair of terminals by a Manhattan path, that is, a path consisting of axis-parallel segments whose total length equals the pairs Manhattan distance. Even for $d=2$, the problem is NP-hard, but constant-factor approximations are known. For $d ge 3$, the problem is APX-hard; it is known to admit, for any $eps > 0$, an $O(n^eps)$-approximation. In the generalized minimum Manhattan network problem (GMMN), we are given a set $R$ of $n$ terminal pairs, and the goal is to find a minimum-length rectilinear network such that each pair in $R$ is connected by a Manhattan path. GMMN is a generalization of both MMN and the well-known rectilinear Steiner arborescence problem (RSA). So far, only special cases of GMMN have been considered. We present an $O(log^{d+1} n)$-approximation algorithm for GMMN (and, hence, MMN) in $d ge 2$ dimensions and an $O(log n)$-approximation algorithm for 2D. We show that an existing $O(log n)$-approximation algorithm for RSA in 2D generalizes easily to $d>2$ dimensions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
