اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the Planar Two-Center Problem and Circular Hulls
124
0
0.0
(
0
)
تأليف
Haitao Wang
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 i
n 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 t
he 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 s
pace 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
