Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Minimum-Area Rectangular and Square Annulus Problem
57
0
0.0
(
0
)
Added by
Sang Won Bae
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Sang Won Bae
Ask ChatGPT about the research
No Arabic abstract
In this paper, we address the minimum-area rectangular and square annulus problem, which asks a rectangular or square annulus of minimum area, either in a fixed orientation or over all orientations, that encloses a set $P$ of $n$ input points in the plane. To our best knowledge, no nontrivial results on the problem have been discussed in the literature, while its minimum-width variants have been intensively studied. For a fixed orientation, we show reductions to well-studied problems: the minimum-width square annulus problem and the largest empty rectangle problem, yielding algorithms of time complexity $O(nlog^2 n)$ and $O(nlog n)$ for the rectangular and square cases, respectively. In arbitrary orientation, we present $O(n^3)$-time algorithms for the rectangular and square annulus problem by enumerating all maximal empty rectangles over all orientations. The same approach is shown to apply also to the minimum-width square annulus problem and the largest empty square problem over all orientations, resulting in $O(n^3)$-time algorithms for both problems. Consequently, we improve the previously best algorithm for the minimum-width square annulus problem by a factor of logarithm, and present the first algorithm for the largest empty square problem in arbitrary orientation. We also consider bicriteria optimization variants, computing a minimum-width minimum-area or minimum-area minimum-width annulus.
rate research
Read More
In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of $n$ points in the plane. A double-strip is a closed region in the plane whose boundary consists of four parallel lines and a parallelogram annulus is a closed region between two edge-parallel parallelograms. We present several first algorithms for these problems. Among them are $O(n^2)$ and $O(n^3 log n)$-time algorithms that compute a minimum-width double-strip and parallelogram annulus, respectively, when their orientations can be freely chosen.
In this paper, we study different variations of minimum width color-spanning annulus problem among a set of points $P={p_1,p_2,ldots,p_n}$ in $I!!R^2$, where each point is assigned with a color in ${1, 2, ldots, k}$. We present algorithms for finding a minimum width color-spanning axis parallel square annulus $(CSSA)$, minimum width color spanning axis parallel rectangular annulus $(CSRA)$, and minimum width color-spanning equilateral triangular annulus of fixed orientation $(CSETA)$. The time complexities of computing (i) a $CSSA$ is $O(n^3+n^2klog k)$ which is an improvement by a factor $n$ over the existing result on this problem, (ii) that for a $CSRA$ is $O(n^4log n)$, and for (iii) a $CSETA$ is $O(n^3k)$. The space complexity of all the algorithms is $O(k)$.
In this article, we study the Euclidean minimum spanning tree problem in an imprecise setup. The problem is known as the emph{Minimum Spanning Tree Problem with Neighborhoods} in the literature. We study the problem where the neighborhoods are represented as non-crossing line segments. Given a set ${cal S}$ of $n$ disjoint line segments in $I!!R^2$, the objective is to find a minimum spanning tree (MST) that contains exactly one end-point from each segment in $cal S$ and the cost of the MST is minimum among $2^n$ possible MSTs. We show that finding such an MST is NP-hard in general, and propose a $2alpha$-factor approximation algorithm for the same, where $alpha$ is the approximation factor of the best-known approximation algorithm to compute a minimum cost Steiner tree in an undirected graph with non-negative edge weights. As an implication of our reduction, we can show that the unrestricted version of the problem (i.e., one point must be chosen from each segment such that the cost of MST is as minimum as possible) is also NP-hard. We also propose a parameterized algorithm for the problem based on the separability parameter defined for segments.
Tusnadys problem asks to bound the discrepancy of points and axis-parallel boxes in $mathbb{R}^d$. Algorithmic bounds on Tusnadys problem use a canonical decomposition of Matouv{s}ek for the system of points and axis-parallel boxes, together with other techniques like partial coloring and / or random-walk based methods. We use the notion of emph{shallow cell complexity} and the emph{shallow packing lemma}, together with the chaining technique, to obtain an improved decomposition of the set system. Coupled with an algorithmic technique of Bansal and Garg for discrepancy minimization, which we also slightly extend, this yields improved algorithmic bounds on Tusnadys problem. For $dgeq 5$, our bound matches the lower bound of $Omega(log^{d-1}n)$ given by Matouv{s}ek, Nikolov and Talwar [IMRN, 2020] -- settling Tusnadys problem, upto constant factors. For $d=2,3,4$, we obtain improved algorithmic bounds of $O(log^{7/4}n)$, $O(log^{5/2}n)$ and $O(log^{13/4}n)$ respectively, which match or improve upon the non-constructive bounds of Nikolov for $dgeq 3$. Further, we also give improved bounds for the discrepancy of set systems of points and polytopes in $mathbb{R}^d$ generated via translations of a fixed set of hyperplanes. As an application, we also get a bound for the geometric discrepancy of anchored boxes in $mathbb{R}^d$ with respect to an arbitrary measure, matching the upper bound for the Lebesgue measure, which improves on a result of Aistleitner, Bilyk, and Nikolov [MC and QMC methods, emph{Springer, Proc. Math. Stat.}, 2018] for $dgeq 4$.
We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the $1$-dimensional homology classes with $mathbb{Z}_2$ coefficients in a given simplicial complex $K$. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al., runs in $O(N^omega + N^2 g)$ time, where $N$ denotes the number of simplices in $K$, $g$ denotes the rank of the $1$-homology group of $K$, and $omega$ denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex $K$. The first algorithm runs in $tilde{O}(m^omega)$ time, where $m$ denotes the number of edges in $K$, whereas the second algorithm runs in $O(m^omega + N m^{omega-1})$ time. We also study the problem of finding a minimum cycle basis in an undirected graph $G$ with $n$ vertices and $m$ edges. The best known algorithm for this problem runs in $O(m^omega)$ time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in $tilde{O}(m^omega)$ time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
