Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShortcut Hulls: Vertex-restricted Outer Simplifications of Polygons
416
0
0.0
(
0
)
Added by
Annika Bonerath
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $P$ be a crossing-free polygon and $mathcal C$ a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of $P$. A shortcut hull of $P$ is another crossing-free polygon that encloses $P$ and whose oriented boundary is composed of elements from $mathcal C$. Shortcut hulls find their application in geo-related problems such as the simplification of contour lines. We aim at a shortcut hull that linearly balances the enclosed area and perimeter. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via shortest paths. For the more challenging case that the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygons exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for drawing the rough extent of point sets as well as for the schematization of polygons.
rate research
Read More
Computation of the vertices of the convex hull of a set $S$ of $n$ points in $mathbb{R} ^m$ is a fundamental problem in computational geometry, optimization, machine learning and more. We present All Vertex Triangle Algorithm (AVTA), a robust and efficient algorithm for computing the subset $overline S$ of all $K$ vertices of $conv(S)$, the convex hull of $S$. If $Gamma_*$ is the minimum of the distances from each vertex to the convex hull of the remaining vertices, given any $gamma leq gamma_* = Gamma_*/R$, $R$ the diameter of $S$, $AVTA$ computes $overline S$ in $O(nK(m+ gamma^{-2}))$ operations. If $gamma_*$ is unknown but $K$ is known, AVTA computes $overline S$ in $O(nK(m+ gamma_*^{-2})) log(gamma_*^{-1})$ operations. More generally, given $t in (0,1)$, AVTA computes a subset $overline S^t$ of $overline S$ in $O(n |overline S^t|(m+ t^{-2}))$ operations, where the distance between any $p in conv(S)$ to $conv(overline S^t)$ is at most $t R$. Next we consider AVTA where input is $S_varepsilon$, an $varepsilon$ perturbation of $S$. Assuming a bound on $varepsilon$ in terms of the minimum of the distances of vertices of $conv(S)$ to the convex hull of the remaining point of $S$, we derive analogous complexity bounds for computing $overline S_varepsilon$. We also analyze AVTA under random projections of $S$ or $S_varepsilon$. Finally, via AVTA we design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. For topic models AVTA leads to significantly better reconstruction of the topic-word matrix than state of the art approaches~cite{arora2013practical, bansal2014provable}. For non-negative matrix AVTA is competitive with existing methods~cite{arora2012computing}. Empirically AVTA is robust and can handle larger amounts of noise than existing methods.
In this extended abstract, we present a PTAS for guarding the vertices of a weakly-visible polygon $P$ from a subset of its vertices, or in other words, a PTAS for computing a minimum dominating set of the visibility graph of the vertices of $P$. We then show how to obtain a PTAS for vertex guarding $P$s boundary.
We present an $O(nlog n)$-time algorithm that determines whether a given planar $n$-gon is weakly simple. This improves upon an $O(n^2log n)$-time algorithm by Chang, Erickson, and Xu (2015). Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.
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.
We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of n real numbers. First, we prove that every such grid contains a convex polygon with $Omega$(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d $in$ N), and obtain a tight lower bound of $Omega$(log d--1 n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the largest convex chain in a grid that contains no two points of the same x-or y-coordinate. We show how to efficiently approximate the maximum size of a supported convex polygon up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
