اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPredicates of the 3D Apollonius Diagram
103
0
0.0
(
0
)
تأليف
Manos Kamarianakis
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this thesis we study one of the fundamental predicates required for the construction of the 3D Apollonius diagram (also known as the 3D Additively Weighted Voronoi diagram), namely the EDGECONFLICT predicate: given five sites $S_i, S_j,S_k,S_l,S_m$ that define an edge $e_{ijklm}$ in the 3D Apollonius diagram, and a sixth query site $S_q$, the predicate determines the portion of $e_{ijklm}$ that will disappear in the Apollonius diagram of the six sites due to the insertion of $S_q$. Our focus is on the algorithmic analysis of the predicate with the aim to minimize its algebraic degree. We decompose the main predicate into sub-predicates, which are then evaluated with the aid of additional primitive operations. We show that the maximum algebraic degree required to answer any of the sub-predicates and primitives, and, thus, our main predicate is 10 in non-degenerate configurations when the trisector is of Hausdorff dimension 1. We also prove that all subpredicates developed can be evaluated using 10 or 8-degree demanding operations for degenerate input for these trisector types, depending on whether they require the evaluation of an intermediate INSPHERE predicate or not. Among the tools we use is the 3D inversion transformation and the so-called qualitative symbolic perturbation scheme. Most of our analysis is carried out in the inverted space, which is where our geometric observations and analysis is captured in algebraic terms.
قيم البحث
اقرأ أيضاً
The morphometric approach [HRC13,RHK06] writes the solvation free energy as a linear combination of weight
Representing an atom by a solid sphere in $3$-dimensional Euclidean space, we get the space-filling diagram of a molecule by taking the union. Molecular dynamics simulates its motion subject to bonds and other forces, including the solvation free ene
rgy. The morphometric approach [HRC13,RHK06] writes the latter as a linear combination of weight
Throughout this paper, a persistence diagram ${cal P}$ is composed of a set $P$ of planar points (each corresponding to a topological feature) above the line $Y=X$, as well as the line $Y=X$ itself, i.e., ${cal P}=Pcup{(x,y)|y=x}$. Given a set of per
sistence diagrams ${cal P}_1,...,{cal P}_m$, for the data reduction purpose, one way to summarize their topological features is to compute the {em center} ${cal C}$ of them first under the bottleneck distance. We consider two discre
Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric.
We present an $O(nloglog n+mlog m)$- time algorithm to compute the geodesic farthest-point Voronoi diagram of $m$ point sites in a simple $n$-gon. This improves the previously best known algorithm by Aronov et al. [Discrete Comput. Geom. 9(3):217-255, 1993]. In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in $O((n + m) log log n)$ time.
Let $P$ be a simple polygon with $n$ vertices. For any two points in $P$, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in $P$. Given a set $S$ of $m$ sites being a subset of the ve
rtices of $P$, we present a randomized algorithm to compute the geodesic farthest-point Voronoi diagram of $S$ in $P$ running in expected $O(n + m)$ time. That is, a partition of $P$ into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic distance. In particular, this algorithm can be extended to run in expected $O(n + mlog m)$ time when $S$ is an arbitrary set of $m$ sites contained in $P$, thereby solving the open problem posed by Mitchell in Chapter 27 of the Handbook of Computational Geometry.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
