Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWorst-Case Optimal Covering of Rectangles by Disks
120
0
0.0
(
0
)
Added by
Phillip Keldenich
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We provide a tight result for a fundamental problem arising from packing disks into a circular container: The critical density of packing disks in a disk is 0.5. This implies that any set of (not necessarily equal) disks of total area $deltaleq 1/2$ can always be packed into a disk of area 1; on the other hand, for any $varepsilon>0$ there are sets of disks of area $1/2+varepsilon$ that cannot be packed. The proof uses a careful manual analysis, complemented by a minor automatic part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms.
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $delta=frac{8}{5pi}approx 0.509$. This implies that any set of (not necessarily equal) squares of total area $A leq frac{8}{5}$ can always be packed into a disk with radius 1; in contrast, for any $varepsilon>0$ there are sets of squares of total area $frac{8}{5}+varepsilon$ that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square $left(frac{1}{2}right)$, circles in a square $left(frac{pi}{(3+2sqrt{2})}approx 0.539right)$ and circles in a circle $left(frac{1}{2}right)$ have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.
Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of $n$ disks in the plane. Initially, all disks have radius $0$, and they grow at constant, but possibly different, speeds. Whenever two disks touch, the one with the higher index disappears. The goal is to determine the elimination order, i.e., the order in which the disks disappear. We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes (e.g., rectangles), and it works in any fixed dimension. We also describe an alternative algorithm that is based on quadtrees. Its running time is $Obig(n big(log n + min { log Delta, log Phi }big)big)$, where $Delta$ is the ratio of the fastest and the slowest growth rate and $Phi$ is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EuroCG 2017]. Finally, we give an $Omega(nlog n)$ lower bound, showing that our quadtree algorithms are almost tight.
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a constant-factor approximate maximum independent set for broad classes of fat objects in $d$ dimensions, where $d$ is assumed to be a constant, in sublinear textit{worst-case} update time. This gives the first results for dynamic independent set in a wide variety of geometric settings, such as disks, fat polygons, and their high-dimensional equivalents. For axis-aligned squares and hypercubes, our result improves upon all (recently announced) previous works. We obtain, in particular, a dynamic $(4+epsilon)$-approximation for squares, with $O(log^4 n)$ worst-case update time. Our result is obtained via a two-level approach. First, we develop a dynamic data structure which stores all objects and provides an approximate independent set when queried, with output-sensitive running time. We show that via standard methods such a structure can be used to obtain a dynamic algorithm with textit{amortized} update time bounds. Then, to obtain worst-case update time algorithms, we develop a generic deamortization scheme that with each insertion/deletion keeps (i) the update time bounded and (ii) the number of changes in the independent set constant. We show that such a scheme is applicable to fat objects by showing an appropriate generalization of a separator theorem. Interestingly, we show that our deamortization scheme is also necessary in order to obtain worst-case update bounds: If for a class of objects our scheme is not applicable, then no constant-factor approximation with sublinear worst-case update time is possible. We show that such a lower bound applies even for seemingly simple classes of geometric objects including axis-aligned rectangles in the plane.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
