Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEmpty Squares in Arbitrary Orientation Among Points
47
0
0.0
(
0
)
Added by
Sang Won Bae
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper studies empty squares in arbitrary orientation among a set $P$ of $n$ points in the plane. We prove that the number of empty squares with four contact pairs is between $Omega(n)$ and $O(n^2)$, and that these bounds are tight, provided $P$ is in a certain general position. A contact pair of a square is a pair of a point $pin P$ and a side $ell$ of the square with $pin ell$. The upper bound $O(n^2)$ also applies to the number of empty squares with four contact points, while we construct a point set among which there is no square of four contact points. These combinatorial results are based on new observations on the $L_infty$ Voronoi diagram with the axes rotated and its close connection to empty squares in arbitrary orientation. We then present an algorithm that maintains a combinatorial structure of the $L_infty$ Voronoi diagram of $P$, while the axes of the plane continuously rotates by $90$ degrees, and simultaneously reports all empty squares with four contact pairs among $P$ in an output-sensitive way within $O(slog n)$ time and $O(n)$ space, where $s$ denotes the number of reported squares. Several new algorithmic results are also obtained: a largest empty square among $P$ and a square annulus of minimum width or minimum area that encloses $P$ over all orientations can be computed in worst-case $O(n^2 log n)$ time.
rate research
Read More
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$.
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. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in $O(nlog n)$ time and $O(nlog n)$ space, where $n$ is the total number of vertices of all obstacles. The algorithm is time-optimal because $Omega(nlog n)$ is a lower bound. It has been an open problem for over two decades whether the space can be reduced to $O(n)$. In this paper, we settle it by solving the problem in $O(nlog n)$ time and $O(n)$ space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point $s$ in $O(nlog n)$ time and $O(n)$ space, such that given any query point $t$, the length of a shortest path from $s$ to $t$ can be computed in $O(log n)$ time and a shortest path can be produced in additional time linear in the number of edges of the path.
This paper presents an optimal $Theta(n log n)$ algorithm for determining time-minimal rectilinear paths among $n$ transient rectilinear obstacles. An obstacle is transient if it exists in the scene only for a specific time interval, i.e., it appears and then disappears at specific times. Given a point robot moving with bounded speed among transient rectilinear obstacles and a pair of points $s$, $d$, we determine a time-minimal, obstacle-avoiding path from $s$ to $d$. The main challenge in solving this problem arises as the robot may be required to wait for an obstacle to disappear, before it can continue moving toward the destination. Our algorithm builds on the continuous Dijkstra paradigm, which simulates propagating a wavefront from the source point. We also solve a query version of this problem. For this, we build a planar subdivision with respect to a fixed source point, so that minimum arrival time to any query point can be reported in $O(log n)$ time, using point location for the query point in this subdivision.
We study three orientation-based shape descriptors on a set of continuously moving points: the first principal component, the smallest oriented bounding box and the thinnest strip. Each of these shape descriptors essentially defines a cost capturing the quality of the descriptor and uses the orientation that minimizes the cost. This optimal orientation may be very unstable as the points are moving, which is undesirable in many practical scenarios. If we bound the speed with which the orientation of the descriptor may change, this may lower the quality of the resulting shape descriptor. In this paper we study the trade-off between stability and quality of these shape descriptors. We first show that there is no stateless algorithm, an algorithm that keeps no state over time, that both approximates the minimum cost of a shape descriptor and achieves continuous motion for the shape descriptor. On the other hand, if we can use the previous state of the shape descriptor to compute the new state, we can define chasing algorithms that attempt to follow the optimal orientation with bounded speed. We show that, under mild conditions, chasing algorithms with sufficient bounded speed approximate the optimal cost at all times for oriented bounding boxes and strips. The analysis of such chasing algorithms is challenging and has received little attention in literature, hence we believe that our methods used in this analysis are of independent interest.
The Euclidean TSP with neighborhoods (TSPN) problem seeks a shortest tour that visits a given collection of $n$ regions ({em neighborhoods}). We present the first polynomial-time approximation scheme for TSPN for a set of regions given by arbitrary disjoint fat regions in the plane. This improves substantially upon the known approximation algorithms, and is the first PTAS for TSPN on regions of non-comparable sizes. Our result is based on a novel extension of the $m$-guillotine method. The result applies to regions that are fat in a very weak sense: each region $P_i$ has area $Omega([diam(P_i)]^2)$, but is otherwise arbitrary.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
