Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon
130
0
0.0
(
0
)
Added by
Omrit Filtser
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $kappa :X rightarrow mathcal{N}$, and a constant $alpha geq 1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x in X$ be covered by at least $kappa(x)$ of the server disks. The objective function we wish to minimize is the sum of the $alpha$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.
Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding box and preserves the orthogonal order i.e. maintains the sorted ordering of the rectangle centers along both $x$-axis and $y$-axis with respect to the initial placement. This problem is known as Layout Adjustment for Disjoint Rectangles(LADR). It was known that LADR is $mathbb{NP}$-hard, but only heuristics were known for it. We show that a certain decision version of LADR is $mathbb{APX}$-hard, and give a constant factor approximation for LADR.
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 provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building epsilon-nets of size O(1/epsilon log log 1/epsilon) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Bronnimann and Goodrich to build an approximation algorithm from this epsilon-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygons vertices. If a finite set of potential guard locations is not specified, e.g. when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithms running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log OPT)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.
In this paper, we study the problem of coverage planning by a mobile robot with a limited energy budget. The objective of the robot is to cover every point in the environment while minimizing the traveled path length. The environment is initially unknown to the robot. Therefore, it needs to avoid the obstacles in the environment on-the-fly during the exploration. As the robot has a specific energy budget, it might not be able to cover the complete environment in one traversal. Instead, it will need to visit a static charging station periodically in order to recharge its energy. To solve the stated problem, we propose a budgeted depth-first search (DFS)-based exploration strategy that helps the robot to cover any unknown planar environment while bounding the maximum path length to a constant-factor of the shortest-possible path length. Our $O(1)$-approximation guarantee advances the state-of-the-art of log-approximation for this problem. Simulation results show that our proposed algorithm outperforms the current state-of-the-art algorithm both in terms of the traveled path length and run time in all the tested environments with concave and convex obstacles.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
