Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Planar Two-Center Problem and Circular Hulls
124
0
0.0
(
0
)
Added by
Haitao Wang
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Haitao Wang
Ask ChatGPT about the research
No Arabic abstract
Given a set $S$ of $n$ points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of $S$. Previously, Eppstein [SODA97] gave a randomized algorithm of $O(nlog^2n)$ expected time and Chan [CGTA99] presented a deterministic algorithm of $O(nlog^2 nlog^2log n)$ time. In this paper, we propose an $O(nlog^2 n)$ time deterministic algorithm, which improves Chans deterministic algorithm and matches the randomized bound of Eppstein. If $S$ is in convex position, then we solve the problem in $O(nlog nloglog n)$ deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.
rate research
Read More
We study four classical graph problems -- Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems in two restricted settings: (i) collinear points and (ii) equidistant points on a circle. We show that almost all of these problems can be solved in linear time in these constrained, yet non-trivial settings.
The quantum problem of an electron moving in a plane under the field created by two Coulombian centers admits simple analytical solutions for some particular inter-center distances. These elementary eigenfunctions, akin to those found by Demkov for the analogous three dimensional problem, are calculated using the framework of quasi-exact solvability of a pair of entangled ODEs descendants from the Heun equation. A different but interesting situation arises when the two centers have the same strength. In this case completely elementary solutions do not exist.
In this paper, we study a model of simplified four-body problem called planar two-center-two-body problem. In the plane, we have two fixed centers $Q_1=(-chi,0)$, $Q_2=(0,0)$ of masses 1, and two moving bodies $Q_3$ and $Q_4$ of masses $mull 1$. They interact via Newtonian potential. $Q_3$ is captured by $Q_2$, and $Q_4$ travels back and forth between two centers. Based on a model of Gerver, we prove that there is a Cantor set of initial conditions which lead to solutions of the Hamiltonian system whose velocities are accelerated to infinity within finite time avoiding all early collisions. We consider this model as a simplified model for the planar four-body problem case of the Painlev{e} conjecture.
For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.
For a polygonal domain with $h$ holes and a total of $n$ vertices, we present algorithms that compute the $L_1$ geodesic diameter in $O(n^2+h^4)$ time and the $L_1$ geodesic center in $O((n^4+n^2 h^4)alpha(n))$ time, respectively, where $alpha(cdot)$ denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $O(n^{7.73})$ or $O(n^7(h+log n))$ time, and compute the geodesic center in $O(n^{11}log n)$ time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $L_1$ shortest paths in polygonal domains.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
