Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Reallocation Algorithm for Online Split Packing of Circles
109
0
0.0
(
0
)
Added by
Shunhao Oh
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Split Packing algorithm cite{splitpacking_ws, splitpackingsoda, splitpacking} is an offline algorithm that packs a set of circles into triangles and squares up to critical density. In this paper, we develop an online alternative to Split Packing to handle an online sequence of insertions and deletions, where the algorithm is allowed to reallocate circles into new positions at a cost proportional to their areas. The algorithm can be used to pack circles into squares and right angled triangles. If only insertions are considered, our algorithm is also able to pack to critical density, with an amortised reallocation cost of $O(clog frac{1}{c})$ for squares, and $O(c(1+s^2)log_{1+s^2}frac{1}{c})$ for right angled triangles, where $s$ is the ratio of the lengths of the second shortest side to the shortest side of the triangle, when inserting a circle of area $c$. When insertions and deletions are considered, we achieve a packing density of $(1-epsilon)$ of the critical density, where $epsilon>0$ can be made arbitrarily small, with an amortised reallocation cost of $O(c(1+s^2)log_{1+s^2}frac{1}{c} + cfrac{1}{epsilon})$.
rate research
Read More
We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.
We consider online packing problems where we get a stream of axis-parallel rectangles. The rectangles have to be placed in the plane without overlapping, and each rectangle must be placed without knowing the subsequent rectangles. The goal is to minimize the perimeter or the area of the axis-parallel bounding box of the rectangles. We either allow rotations by 90 degrees or translations only. For the perimeter version we give algorithms with an absolute competitive ratio slightly less than 4 when only translations are allowed and when rotations are also allowed. We then turn our attention to minimizing the area and show that the asymptotic competitive ratio of any algorithm is at least $Omega(sqrt{n})$, where $n$ is the number of rectangles in the stream, and this holds with and without rotations. We then present algorithms that match this bound in both cases. We also show that the competitive ratio cannot be bounded as a function of OPT. We then consider two special cases. The first is when all the given rectangles have aspect ratios bounded by some constant. The particular variant where all the rectangles are squares and we want to minimize the area of the bounding square has been studied before and an algorithm with a competitive ratio of 8 has been given [Fekete and Hoffmann, Algorithmica, 2017]. We improve the analysis of the algorithm and show that the ratio is at most 6, which is tight. The second special case is when all edges have length at least 1. Here, the $Omega(sqrt n)$ lower bound still holds, and we turn our attention to lower bounds depending on OPT. We show that any algorithm has an asymptotic competitive ratio of at least $Omega(sqrt{OPT})$ for the translational case and $Omega(sqrt[4]{OPT})$ when rotations are allowed. For bo
We consider the online search problem in which a server starting at the origin of a $d$-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the $d$-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in $Omega(d)cap O(d^{3/2})$.
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri [SIAM J. Comput. 1999] gave an algorithm of $O(nlog n)$ time and $O(nlog n)$ space, where $n$ is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suris algorithm, Wang [SODA 2021] reduced the space to $O(n)$ while the runtime of the algorithm is still $O(nlog n)$. In this paper, we present a new algorithm of $O(n+hlog h)$ time and $O(n)$ space, provided that a triangulation of the free space is given, where $h$ is the number of obstacles. The algorithm, which improves the previous work when $h=o(n)$, is optimal in both time and space as $Omega(n+hlog h)$ is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point $s$, so that given any query point $t$, the shortest path length from $s$ to $t$ can be computed in $O(log n)$ time and a shortest $s$-$t$ path can be produced in additional time linear in the number of edges of the path.
A polyomino is a polygonal region with axis parallel edges and corners of integral coordinates, which may have holes. In this paper, we consider planar tiling and packing problems with polyomino pieces and a polyomino container $P$. We give two polynomial time algorithms, one for deciding if $P$ can be tiled with $ktimes k$ squares for any fixed $k$ which can be part of the input (that is, deciding if $P$ is the union of a set of non-overlapping $ktimes k$ squares) and one for packing $P$ with a maximum number of non-overlapping and axis-parallel $2times 1$ dominos, allowing rotations by $90^circ$. As packing is more general than tiling, the latter algorithm can also be used to decide if $P$ can be tiled by $2times 1$ dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of $2times 2$ squares is known to be NP-Hard [J. Algorithms 1990]. For our three problems there are known pseudo-polynomial time algorithms, that is, algorithms with running times polynomial in the area of $P$. However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial time algorithms for the problems. Concretely, we give a simple $O(nlog n)$ algorithm for tiling with squares, and a more involved $O(n^3,text{polylog}, n)$ algorithm for packing and tiling with dominos, where $n$ is the number of corners of $P$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
