Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUpper bounds for stabbing simplices by a line
168
0
0.0
(
0
)
Added by
Gabriel Nivasch
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
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$.
The set of points in a metric space is called an $s$-distance set if pairwise distances between these points admit only $s$ distinct values. Two-distance spherical sets with the set of scalar products ${alpha, -alpha}$, $alphain[0,1)$, are called equiangular. The problem of determining the maximum size of $s$-distance sets in various spaces has a long history in mathematics. We suggest a new method of bounding the size of an $s$-distance set in compact two-point homogeneous spaces via zonal spherical functions. This method allows us to prove that the maximum size of a spherical two-distance set in $mathbb{R}^n$, $ngeq 7$, is $frac{n(n+1)}2$ with possible exceptions for some $n=(2k+1)^2-3$, $k in mathbb{N}$. We also prove the universal upper bound $sim frac 2 3 n a^2$ for equiangular sets with $alpha=frac 1 a$ and, employing this bound, prove a new upper bound on the size of equiangular sets in all dimensions. Finally, we classify all equiangular sets reaching this new bound.
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}.
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
