Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeometric k-Center Problems with Centers Constrained to Two Lines
60
0
0.0
(
0
)
Added by
Tsunehiko Kameda
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the $k$-center problem in which the centers are constrained to lie on two lines. Given a set of $n$ weighted points in the plane, we want to locate up to $k$ centers on two parallel lines. We present an $O(nlog^2 n)$ time algorithm, which minimizes the weighted distance from any point to a center. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithms run in $O(nlog^2 n)$ time also in this case.
rate research
Read More
We study the $k$-center problem in a kinetic setting: given a set of continuously moving points $P$ in the plane, determine a set of $k$ (moving) disks that cover $P$ at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model allows positive results only for $k<3$. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of $k$-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution -- the topological stability ratio -- considering various metrics and various optimization criteria. For $k = 2$ we provide tight bounds, and for small $k > 2$ we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant $k$.
The Euclidean $k$-center problem is a classical problem that has been extensively studied in computer science. Given a set $mathcal{G}$ of $n$ points in Euclidean space, the problem is to determine a set $mathcal{C}$ of $k$ centers (not necessarily part of $mathcal{G}$) such that the maximum distance between a point in $mathcal{G}$ and its nearest neighbor in $mathcal{C}$ is minimized. In this paper we study the corresponding $(k,ell)$-center problem for polygonal curves under the Frechet distance, that is, given a set $mathcal{G}$ of $n$ polygonal curves in $mathbb{R}^d$, each of complexity $m$, determine a set $mathcal{C}$ of $k$ polygonal curves in $mathbb{R}^d$, each of complexity $ell$, such that the maximum Frechet distance of a curve in $mathcal{G}$ to its closest curve in $mathcal{C}$ is minimized. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension $2$ and higher. We show that, if $ell$ is part of the input, then there is no polynomial-time approximation scheme unless $mathsf{P}=mathsf{NP}$. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Frechet distance. In the case of the discrete Frechet distance on two-dimensional curves, we show hardness of approximation within a factor close to $2.598$. This result also holds when $k=1$, and the $mathsf{NP}$-hardness extends to the case that $ell=infty$, i.e., for the problem of computing the minimum-enclosing ball under the Frechet distance. Finally, we observe that a careful adaptation of Gonzalez algorithm in combination with a curve simplification yields a $3$-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.
We present algorithms for length-constrained maximum sum segment and maximum density segment problems, in particular, and the problem of finding length-constrained heaviest segments, in general, for a sequence of real numbers. Given a sequence of n real numbers and two real parameters L and U (L <= U), the maximum sum segment problem is to find a consecutive subsequence, called a segment, of length at least L and at most U such that the sum of the numbers in the subsequence is maximum. The maximum density segment problem is to find a segment of length at least L and at most U such that the density of the numbers in the subsequence is the maximum. For the first problem with non-uniform width there is an algorithm with time and space complexities in O(n). We present an algorithm with time complexity in O(n) and space complexity in O(U). For the second problem with non-uniform width there is a combinatorial solution with time complexity in O(n) and space complexity in O(U). We present a simple geometric algorithm with the same time and space complexities. We extend our algorithms to respectively solve the length-constrained k maximum sum segments problem in O(n+k) time and O(max{U, k}) space, and the length-constrained $k$ maximum density segments problem in O(n min{k, U-L}) time and O(U+k) space. We present extensions of our algorithms to find all the length-constrained segments having user specified sum and density in O(n+m) and O(nlog (U-L)+m) times respectively, where m is the number of output. Previously, there was no known algorithm with non-trivial result for these problems. We indicate the extensions of our algorithms to higher dimensions. All the algorithms can be extended in a straight forward way to solve the problems with non-uniform width and non-uniform weight.
For any constants $dge 1$, $epsilon >0$, $t>1$, and any $n$-point set $Psubsetmathbb{R}^d$, we show that there is a geometric graph $G=(P,E)$ having $O(nlog^2 nloglog n)$ edges with the following property: For any $Fsubseteq P$, there exists $F^+supseteq F$, $|F^+| le (1+epsilon)|F|$ such that, for any pair $p,qin Psetminus F^+$, the graph $G-F$ contains a path from $p$ to $q$ whose (Euclidean) length is at most $t$ times the Euclidean distance between $p$ and $q$. In the terminology of robust spanners (Bose et al, SICOMP, 42(4):1720--1736, 2013) the graph $G$ is a $(1+epsilon)k$-robust $t$-spanner of $P$. This construction is sparser than the recent constructions of Buchin, Ol`ah, and Har-Peled (arXiv:1811.06898) who prove the existence of $(1+epsilon)k$-robust $t$-spanners with $nlog^{O(d)} n$ edges.
Given a set $P$ of $n$ points and a set $S$ of $m$ weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of $P$. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line $L$ (while points of $P$ can be anywhere in the plane). We present an $O((m+n)log(m+n)+kappalog m)$ time algorithm for the problem, where $kappa$ is the number of pairs of disks that intersect. Alternatively, we can also solve the problem in $O(nmlog(m+n))$ time. For the unit-disk case where all disks have the same radius, the running time can be reduced to $O((n+m)log(m+n))$. In addition, we solve in $O((m+n)log(m+n))$ time the $L_{infty}$ and $L_1$ cases of the problem, in which the disks are squares and diamonds, respectively. As a by-product, the 1D version of the problem where all points of $P$ are on $L$ and the disks are line segments on $L$ is also solved in $O((m+n)log(m+n))$ time. We also show that the problem has an $Omega((m+n)log (m+n))$ time lower bound even for the 1D case. We further demonstrate that our techniques can also be used to solve other geometric coverage problems. For example, given in the plane a set $P$ of $n$ points and a set $S$ of $n$ weighted half-planes, we solve in $O(n^4log n)$ time the problem of finding a subset of half-planes to cover $P$ so that their total weight is minimized. This improves the previous best algorithm of $O(n^5)$ time by almost a linear factor. If all half-planes are lower ones, then our algorithm runs in $O(n^2log n)$ time, which improves the previous best algorithm of $O(n^4)$ time by almost a quadratic factor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
