Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStabbing Pairwise Intersecting Disks by Four Points
129
0
0.0
(
0
)
Added by
Pat Morin
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In their seminal work, Danzer (1956, 1986) and Stach{o} (1981) established that every set of pairwise intersecting disks in the plane can be stabbed by four points. However, both these proofs are non-constructive, at least in the sense that they do not seem to imply an efficient algorithm for finding the stabbing points, given such a set of disks $D$. Recently, Har-Peled etal (2018) presented a relatively simple linear-time algorithm for finding five points that stab $D$. We present an alternative proof (and the first in English) to the assertion that four points are sufficient to stab $D$. Moreover, our proof is constructive and provides a simple linear-time algorithm for finding the stabbing points. As a warmup, we present a nearly-trivial liner-time algorithm with an elementary proof for finding five points that stab $D$.
rate research
Read More
It is known that for every dimension $dge 2$ and every $k<d$ there exists a constant $c_{d,k}>0$ such that for every $n$-point set $Xsubset mathbb R^d$ there exists a $k$-flat that intersects at least $c_{d,k} n^{d+1-k} - o(n^{d+1-k})$ of the $(d-k)$-dimensional simplices spanned by $X$. However, the optimal values of the constants $c_{d,k}$ are mostly unknown. The case $k=0$ (stabbing by a point) has received a great deal of attention. In this paper we focus on the case $k=1$ (stabbing by a line). Specifically, we try to determine the upper bounds yielded by two point sets, known as the stretched grid and the stretched diagonal. Even though the calculations are independent of $n$, they are still very complicated, so we resort to analytical and numerical software methods. We provide strong evidence that, surprisingly, for $d=4,5,6$ the stretched grid yields better bounds than the stretched diagonal (unlike for all cases $k=0$ and for the case $(d,k)=(3,1)$, in which both point sets yield the same bound). Our experiments indicate that the stretched grid yields $c_{4,1}leq 0.00457936$, $c_{5,1}leq 0.000405335$, and $c_{6,1}leq 0.0000291323$.
We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network design. To the best of our knowledge, only special cases of this problem have been considered so far. Stabbing is a weighted geometric set cover problem, which we show to be NP-hard. A constrained variant of Stabbing turns out to be even APX-hard. While for general set cover the best possible approximation ratio is $Theta(log n)$, it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODA12] generalize earlier results by Varadarajan [STOC10] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity. Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.
Let $P subseteq mathbb{R}^2$ be a set of points and $T$ be a spanning tree of $P$. The emph{stabbing number} of $T$ is the maximum number of intersections any line in the plane determines with the edges of $T$. The emph{tree stabbing number} of $P$ is the minimum stabbing number of any spanning tree of $P$. We prove that the tree stabbing number is not a monotone parameter, i.e., there exist point sets $P subsetneq P$ such that treestab{$P$} $>$ treestab{$P$}, answering a question by Eppstein cite[Open Problem~17.5]{eppstein_2018}.
We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any $lambdageq 1$, the critical covering area $A^*(lambda)$ is the minimum value for which any set of disks with total area at least $A^*(lambda)$ can cover a rectangle of dimensions $lambdatimes 1$. We show that there is a threshold value $lambda_2 = sqrt{sqrt{7}/2 - 1/4} approx 1.035797ldots$, such that for $lambda<lambda_2$ the critical covering area $A^*(lambda)$ is $A^*(lambda)=3pileft(frac{lambda^2}{16} +frac{5}{32} + frac{9}{256lambda^2}right)$, and for $lambdageq lambda_2$, the critical area is $A^*(lambda)=pi(lambda^2+2)/4$; these values are tight. For the special case $lambda=1$, i.e., for covering a unit square, the critical covering area is $frac{195pi}{256}approx 2.39301ldots$. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.
We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by branching on an inequality and its integer negation. That is, we can (nondeterministically choose) a hyperplane a x geq b with integer coefficients, which partitions the polytope into three pieces: the points in the polytope satisfying a x geq b, the points satisfying a x leq b-1, and the middle slab b-1 < a x < b. Since the middle slab contains no integer points it can be safely discarded, and the algorithm proceeds recursively on the other two branches. Each path terminates when the current polytope is empty, which is polynomial-time checkable. Among our results, we show somewhat surprisingly that Stabbing Planes can efficiently simulate Cutting Planes, and moreover, is strictly stronger than Cutting Planes under a reasonable conjecture. We prove linear lower bounds on the rank of Stabbing Planes refutations, by adapting a lifting argument in communication complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
