The Experts below are selected from a list of 315 Experts worldwide ranked by ideXlab platform
Csaba D. Tóth - One of the best experts on this subject based on the ideXlab platform.
-
anchored Rectangle and square packings
Discrete Optimization, 2017Co-Authors: Adrian Dumitrescu, Csaba D. Tóth, Kevin BalasAbstract:Abstract For points p 1 , … , p n in the unit square [ 0 , 1 ] 2 , an anchored Rectangle packing consists of interior-disjoint axis-aligned empty Rectangles r 1 , … , r n ⊆ [ 0 , 1 ] 2 such that point p i is a corner of the Rectangle r i (that is, r i is anchored at p i ) for i = 1 , … , n . We show that for every set of n points in [ 0 , 1 ] 2 , there is an anchored Rectangle packing of area at least 7 ∕ 12 − O ( 1 ∕ n ) , and for every n ∈ N , there are point sets for which the area of every anchored Rectangle packing is at most 2 ∕ 3 . The maximum area of an anchored square packing is always at least 5 ∕ 32 and sometimes at most 7 ∕ 27 . The above constructive lower bounds immediately yield constant-factor approximations, of 7 ∕ 12 − e for Rectangles and 5 ∕ 32 for squares, for computing anchored packings of maximum area in O ( n log n ) time. We prove that a simple greedy strategy achieves a 9 ∕ 47 -approximation for anchored square packings, and 1 ∕ 3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS for anchored Rectangle packings in exp ( poly ( e − 1 log n ) ) time and a PTAS for anchored square packings in n O ( 1 ∕ e ) time.
-
Anchored Rectangle and Square Packings
arXiv: Computational Geometry, 2016Co-Authors: Kevin Balas, Adrian Dumitrescu, Csaba D. TóthAbstract:For points $p_1,\ldots , p_n$ in the unit square $[0,1]^2$, an \emph{anchored Rectangle packing} consists of interior-disjoint axis-aligned empty Rectangles $r_1,\ldots , r_n\subseteq [0,1]^2$ such that point $p_i$ is a corner of the Rectangle $r_i$ (that is, $r_i$ is \emph{anchored} at $p_i$) for $i=1,\ldots, n$. We show that for every set of $n$ points in $[0,1]^2$, there is an anchored Rectangle packing of area at least $7/12-O(1/n)$, and for every $n\in \mathbf{N}$, there are point sets for which the area of every anchored Rectangle packing is at most $2/3$. The maximum area of an anchored \emph{square} packing is always at least $5/32$ and sometimes at most $7/27$. The above constructive lower bounds immediately yield constant-factor approximations, of $7/12 -\varepsilon$ for Rectangles and $5/32$ for squares, for computing anchored packings of maximum area in $O(n\log n)$ time. We prove that a simple greedy strategy achieves a $9/47$-approximation for anchored square packings, and $1/3$ for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored Rectangle and square packings in $n^{O(1/\varepsilon)}$ and $\exp({\rm poly}(\log (n/\varepsilon)))$ time, respectively.
-
anchored Rectangle and square packings
Symposium on Computational Geometry, 2016Co-Authors: Kevin Balas, Adrian Dumitrescu, Csaba D. TóthAbstract:For points p_1,...,p_n in the unit square [0,1]^2, an anchored Rectangle packing consists of interior-disjoint axis-aligned empty Rectangles r_1,...,r_n in [0,1]^2 such that point p_i is a corner of the Rectangle r_i (that is, r_i is anchored at p_i) for i=1,...,n. We show that for every set of n points in [0,1]^2, there is an anchored Rectangle packing of area at least 7/12-O(1/n), and for every n, there are point sets for which the area of every anchored Rectangle packing is at most 2/3. The maximum area of an anchored square packing is always at least 5/32 and sometimes at most 7/27. The above constructive lower bounds immediately yield constant-factor approximations, of 7/12 -epsilon for Rectangles and 5/32 for squares, for computing anchored packings of maximum area in O(n log n) time. We prove that a simple greedy strategy achieves a 9/47-approximation for anchored square packings, and 1/3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored Rectangle and square packings in n^{O(1/epsilon)} and exp(poly(log (n/epsilon))) time, respectively.
-
SODA - Packing anchored Rectangles
2012Co-Authors: Adrian Dumitrescu, Csaba D. TóthAbstract:Let S be a set of n points in the unit square [0, 1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty Rectangles such that the lower left corner of each Rectangle is a point in S, and the Rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the Rectangles in such a packing can jointly cover an area of at least 1/2.
-
Packing anchored Rectangles
arXiv: Combinatorics, 2011Co-Authors: Adrian Dumitrescu, Csaba D. TóthAbstract:Let $S$ be a set of $n$ points in the unit square $[0,1]^2$, one of which is the origin. We construct $n$ pairwise interior-disjoint axis-aligned empty Rectangles such that the lower left corner of each Rectangle is a point in $S$, and the Rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the Rectangles in such a packing can jointly cover an area of at least 1/2.
Apurva Mudgal - One of the best experts on this subject based on the ideXlab platform.
-
Approximability and hardness of geometric hitting set with axis-parallel Rectangles
Information Processing Letters, 2019Co-Authors: Raghunath Reddy Madireddy, Apurva MudgalAbstract:Abstract We show that geometric hitting set with axis-parallel Rectangles is APX -hard even when all Rectangles share a common point. We also show that geometric hitting set problem is APX -hard for several classes of objects given in [3] such as axis-parallel ellipses with a shared point, axis-parallel cubes sharing a common point, etc. Further, we give a polynomial time approximation scheme ( PTAS ) for the weighted hitting set problem with axis-parallel Rectangles when all Rectangles have integer side lengths bounded by a constant C . Finally, we show that the problem is NP -hard for Rectangles of size 1 × 2 and 2 × 1 even when every Rectangle intersects a given unit height horizontal strip.
Mikael Östling - One of the best experts on this subject based on the ideXlab platform.
-
Percolation thresholds of two-dimensional continuum systems of Rectangles [with erratum]
arXiv: Data Analysis Statistics and Probability, 2016Co-Authors: Jiantong Li, Mikael ÖstlingAbstract:The present work introduces an efficient Monte Carlo algorithm for continuum percolation composed of randomly-oriented Rectangles. By conducting extensive simulations, we report high precision percolation thresholds for a variety of homogeneous systems with different Rectangle aspect ratios. This work verifies and extends the excluded area theory. It is confirmed that percolation thresholds are dominated by the average excluded areas for both homogeneous and heterogeneous Rectangle systems (except for some special heterogeneous systems where the Rectangle lengths differ too much from one another). In terms of the excluded areas, generalized formulae are proposed to effectively predict precise percolation thresholds for all these Rectangle systems. This work is therefore helpful for both practical applications and theoretical studies concerning relevant systems. The Erratum addresses errors in our earlier paper "Percolation thresholds of two-dimensional continuum systems of Rectangles" published in [Phys. Rev. E 88, 012101 (2013)].
-
Percolation thresholds of two-dimensional continuum systems of Rectangles.
Physical Review E, 2013Co-Authors: Jiantong Li, Mikael ÖstlingAbstract:The present paper introduces an efficient Monte Carlo algorithm for continuum percolation composed of randomly oriented Rectangles. By conducting extensive simulations, we report high-precision percolation thresholds for a variety of homogeneous systems with different Rectangle aspect ratios. This paper verifies and extends the excluded area theory. It is confirmed that percolation thresholds are dominated by the average excluded areas for both homogeneous and heterogeneous Rectangle systems (except for some special heterogeneous systems where the Rectangle lengths differ too much from one another). In terms of the excluded areas, generalized formulas are proposed to effectively predict precise percolation thresholds for all these Rectangle systems. This paper is, therefore, helpful for both practical applications and theoretical studies concerning relevant systems.
Hee-kap Ahn - One of the best experts on this subject based on the ideXlab platform.
-
Maximum-Area Rectangles in a Simple Polygon
arXiv: Computational Geometry, 2019Co-Authors: Yujin Choi, Seungjun Lee, Hee-kap AhnAbstract:We study the problem of finding maximum-area Rectangles contained in a polygon in the plane. There has been a fair amount of work for this problem when the Rectangles have to be axis-aligned or when the polygon is convex. We consider this problem in a simple polygon with $n$ vertices, possibly with holes, and with no restriction on the orientation of the Rectangles. We present an algorithm that computes a maximum-area Rectangle in $O(n^3\log n)$ time using $O(kn^2)$ space, where $k$ is the number of reflex vertices of $P$. Our algorithm can report all maximum-area Rectangles in the same time using $O(n^3)$ space. We also present a simple algorithm that finds a maximum-area Rectangle contained in a convex polygon with $n$ vertices in $O(n^3)$ time using $O(n)$ space.
-
covering a point set by two disjoint Rectangles
International Journal of Computational Geometry and Applications, 2011Co-Authors: Sangsub Kim, Sang Won Bae, Hee-kap AhnAbstract:Given a set S of n points in the plane, the disjoint two-Rectangle covering problem is to find a pair of disjoint Rectangles such that their union contains S and the area of the larger Rectangle is minimized. In this paper we consider two variants of this optimization problem: (1) the Rectangles are allowed to be reoriented freely while restricting them to be parallel to each other, and (2) one Rectangle is restricted to be axis-parallel but the other Rectangle is allowed to be reoriented freely. For both of the problems, we present O(n2log n)-time algorithms using O(n) space.
-
covering a point set by two disjoint Rectangles
International Symposium on Algorithms and Computation, 2008Co-Authors: Hee-kap Ahn, Sang Won BaeAbstract:Given a set S of n points in the plane, the disjoint two-Rectangle covering problem is to find a pair of disjoint Rectangles such that their union contains S and the area of the larger Rectangle is minimized. In this paper we consider two variants of this optimization problem: (1) the Rectangles are free to rotate but must remain parallel to each other, and (2) one Rectangle is axis-parallel but the other Rectangle is allowed to have an arbitrary orientation. For both of the problems, we present O(n 2logn)-time algorithms using O(n) space.
-
Maximum-area and maximum-perimeter Rectangles in polygons
Computational Geometry, 1Co-Authors: Yujin Choi, Seungjun Lee, Hee-kap AhnAbstract:Abstract We study the problem of finding maximum-area and maximum-perimeter Rectangles that are inscribed in polygons in the plane. There has been a fair amount of work on this problem when the Rectangles have to be axis-aligned or when the polygons are convex. We consider this problem in polygons with n vertices that are not necessarily convex, possibly with holes, and with no restriction on the orientation of the Rectangles. We present an algorithm that computes a maximum-area Rectangle and a maximum-perimeter Rectangle in O ( n 3 log n ) time using O ( k n 2 + n ) space, where k is the number of reflex vertices of the polygon. Our algorithm can report all maximum-area Rectangles in the same time using O ( n 3 ) space. We also present a simple algorithm that finds a maximum-area Rectangle inscribed in a convex polygon with n vertices in O ( n 3 ) time using O ( n ) space.
Mike Paterson - One of the best experts on this subject based on the ideXlab platform.
-
on approximating Rectangle tiling and packing
Symposium on Discrete Algorithms, 1998Co-Authors: Sanjeev Khanna, S Muthukrishnan, Mike PatersonAbstract:Our study of tiling and packing with Rectangles in two-dimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and motion estimation in video compression by block matching, among others. An example of the problems that we tackle is the following: given an n by n array A of positive numbers, find a tiling using at most p Rectangles (that is, no two Rectangles must overlap, and each array element must fall within some Rectangle) that minimizes the maximum weight of any Rectangle; here the "weight" of a Rectangle is the sum of the array elements that fall within it. If the array A were one-dimensional, this problem could be easily solved by dynamic programming. We prove that in the two-dimensional case it is NP-hard to approximate this problem to within a factor of 1.25. On the other hand, we provide a near-linear time algorithm that returns a solution at most 2.5 times the optimal. Other Rectangle tiling and packing problems that we study have similar properties: while it is easy to solve them optimally in one dimension, the two-dimensional versions become NP-hard. We design efficient approximation algorithms for these problems.
