ﻻ يوجد ملخص باللغة العربية
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.
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 eff
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
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 g
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
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