Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Approximation for Guarding Simple Galleries from the Perimeter
121
0
0.0
(
0
)
Added by
James King
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
An edge guard set of a plane graph $G$ is a subset $Gamma$ of edges of $G$ such that each face of $G$ is incident to an endpoint of an edge in $Gamma$. Such a set is said to guard $G$. We improve the known upper bounds on the number of edges required to guard any $n$-vertex embedded planar graph $G$: 1- We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that $G$ can be guarded with at most $ frac{2n}{5}$ edges, then extend this approach with a deeper analysis to yield an improved bound of $frac{3n}{8}$ edges for any plane graph. 2- We prove that there exists an edge guard set of $G$ with at most $frac{n}{3}+frac{alpha}{9}$ edges, where $alpha$ is the number of quadrilateral faces in $G$. This improves the previous bound of $frac{n}{3} + alpha$ by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in $G$, we show that $frac{n}{3}$ edges suffice, removing the dependence on $alpha$.
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 an arrangement of lines in the plane, what is the minimum number $c$ of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between $Omega (log n / loglog n)$. and $O(sqrt{n})$. Similarly, we give bounds on the minimum size of a subset $S$ of the intersections of the lines in $mathcal{A}$ such that every cell is bounded by at least one of the vertices in $S$. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $Hcellzone$ hypergraph.
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
