Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSmoothed Analysis of the Art Gallery Problem
239
0
0.0
(
0
)
Added by
Tillmann Miltzow
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the Art Gallery Problem we are given a polygon $Psubset [0,L]^2$ on $n$ vertices and a number $k$. We want to find a guard set $G$ of size $k$, such that each point in $P$ is seen by a guard in $G$. Formally, a guard $g$ sees a point $p in P$ if the line segment $pg$ is fully contained inside the polygon $P$. The history and practical findings indicate that irrational coordinates are a very rare phenomenon. We give a theoretical explanation. Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude $delta$ of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an $existsmathbb{R}$-complete problem was analyzed by Smoothed Analysis.
rate research
Read More
In this paper I present several novel, efficient, algorithmic techniques for solving some multidimensional geometric data management and analysis problems. The techniques are based on several data structures from computational geometry (e.g. segment tree and range tree) and on the well-known sweep-line method.
This is the arXiv index for the electronic proceedings of GD 2019, which contains the peer-reviewed and revised accepted papers with an optional appendix. Proceedings (without appendices) are also to be published by Springer in the Lecture Notes in Computer Science series.
This is the arXiv index for the electronic proceedings of GD 2021, which contains the peer-reviewed and revised accepted papers with an optional appendix. Proceedings (without appendices) are also to be published by Springer in the Lecture Notes in Computer Science series.
A classic theorem by Steinitz states that a graph G is realizable by a convex polyhedron if and only if G is 3-connected planar. Zonohedra are an important subclass of convex polyhedra having the property that the faces of a zonohedron are parallelograms and are in parallel pairs. In this paper we give characterization of graphs of zonohedra. We also give a linear time algorithm to recognize such a graph. In our quest for finding the algorithm, we prove that in a zonohedron P both the number of zones and the number of faces in each zone is O(square root{n}), where n is the number of vertices of P.
We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $ell$ such that $ell$ intersects at most $O(sqrt{(m+n)log{n}})$ disks and each of the halfplanes determined by $ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting $O(sqrt{m+n})$ disks exists, but each halfplane may contain up to $4n/5$ disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in $n$ exists when we look at disks of arbitrary radii, even when $m=0$. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size $O(sqrt{m})$).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
