Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the continuous Fermat-Weber problem for a convex polygon using Euclidean distance
109
0
0.0
(
0
)
Added by
John Carlsson
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the continuous Fermat-Weber problem, where the customers are continuously (uniformly) distributed along the boundary of a convex polygon. We derive the closed-form expression for finding the average distance from a given point to the continuously distributed customers along the boundary. A Weiszfeld-type procedure is proposed for this model, which is shown to be linearly convergent. We also derive a closed-form formula to find the average distance for a given point to the entire convex polygon, assuming a uniform distribution. Since the function is smooth, convex, and explicitly given, the continuous version of the Fermat-Weber problem over a convex polygon can be solved easily by numerical algorithms.
rate research
Read More
Clustering has been one of the most basic and essential problems in unsupervised learning due to various applications in many critical fields. The recently proposed sum-of-nums (SON) model by Pelckmans et al. (2005), Lindsten et al. (2011) and Hocking et al. (2011) has received a lot of attention. The advantage of the SON model is the theoretical guarantee in terms of perfect recovery, established by Sun et al. (2018). It also provides great opportunities for designing efficient algorithms for solving the SON model. The semismooth Newton based augmented Lagrangian method by Sun et al. (2018) has demonstrated its superior performance over the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA). In this paper, we propose a Euclidean distance matrix model based on the SON model. An efficient majorization penalty algorithm is proposed to solve the resulting model. Extensive numerical experiments are conducted to demonstrate the efficiency of the proposed model and the majorization penalty algorithm.
Given two sets of points in the plane, $P$ of $n$ terminals and $S$ of $m$ Steiner points, a Steiner tree of $P$ is a tree spanning all points of $P$ and some (or none or all) points of $S$. A Steiner tree with length of longest edge minimized is called a bottleneck Steiner tree. In this paper, we study the Euclidean bottleneck Steiner tree problem: given two sets, $P$ and $S$, and a positive integer $k le m$, find a bottleneck Steiner tree of $P$ with at most $k$ Steiner points. The problem has application in the design of wireless communication networks. We first show that the problem is NP-hard and cannot be approximated within factor $sqrt{2}$, unless $P=NP$. Then, we present a polynomial-time approximation algorithm with performance ratio 2.
Suppose an escaping player moves continuously at maximum speed 1 in the interior of a region, while a pursuing player moves continuously at maximum speed $r$ outside the region. For what $r$ can the first player escape the region, that is, reach the boundary a positive distance away from the pursuing player, assuming optimal play by both players? We formalize a model for this infinitesimally alternating 2-player game that we prove has a unique winner in any region with locally rectifiable boundary, avoiding pathological behaviors (where both players can have winning strategies) previously identified for pursuit-evasion games such as the Lion and Man problem in certain metric spaces. For some regions, including both equilateral triangle and square, we give exact results for the critical speed ratio, above which the pursuing player can win and below which the escaping player can win (and at which the pursuing player can win). For simple polygons, we give a simple formula and polynomial-time algorithm that is guaranteed to give a 10.89898-approximation to the critical speed ratio, and we give a pseudopolynomial-time approximation scheme for arbitrarily approximating the critical speed ratio. On the negative side, we prove NP-hardness of the problem for polyhedral domains in 3D, and prove stronger results (PSPACE-hardness and NP-hardness even to approximate) for generalizations to multiple escaping and pursuing players.
The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time $O(log n)$-approximation algorithm for placing as few guards as possible at vertices of a simple $n$-gon $P$, such that every point in $P$ is visible to at least one of the guards. Ghosh also conjectured that this problem admits a polynomial-time algorithm with constant approximation ratio. Due to the centrality of guarding problems in the field of computational geometry, much effort has been invested throughout the years in trying to resolve this conjecture. Despite some progress (surveyed below), the conjecture remains unresolved to date. In this paper, we confirm the conjecture for the important case of weakly visible polygons, by presenting a $(2+varepsilon)$-approximation algorithm for guarding such a polygon using vertex guards. A simple polygon $P$ is weakly visible if it has an edge $e$, such that every point in $P$ is visible from some point on $e$. We also present a $(2+varepsilon)$-approximation algorithm for guarding a weakly visible polygon $P$, where guards may be placed anywhere on $P$s boundary (except in the interior of the edge $e$). Finally, we present a $3c$-approximation algorithm for vertex guarding a polygon $P$ that is weakly visible from a chord, given a subset $G$ of $P$s vertices that guards $P$s boundary whose size is bounded by $c$ times the size of a minimum such subset. Our algorithms are based on an in-depth analysis of the geometric properties of the regions that remain unguarded after placing guards at the vertices to guard the polygons boundary. It is plausible that our results will enable Bhattacharya et al. to complete their grand attempt to prove the original conjecture, as their approach is based on partitioning the underlying simple polygon into a hierarchy of weakly visible polygons.
Given two shapes $A$ and $B$ in the plane with Hausdorff distance $1$, is there a shape $S$ with Hausdorff distance $1/2$ to and from $A$ and $B$? The answer is always yes, and depending on convexity of $A$ and/or $B$, $S$ may be convex, connected, or disconnected. We show that our result can be generalised to give an interpolated shape between $A$ and $B$ for any interpolation variable $alpha$ between $0$ and $1$, and prove that the resulting morph has a bounded rate of change with respect to $alpha$. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two input sets. We show how to approximate or compute this middle shape, and that the properties relating to the connectedness of the Hausdorff middle extend from the case with two input sets. We also give bounds on the Hausdorff distance between the middle set and the input.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
