Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeodesic farthest-point Voronoi diagram in linear time
102
0
0.0
(
0
)
Added by
Luis Barba
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Luis Barba
Ask ChatGPT about the research
No Arabic abstract
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 vertices 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.
rate research
Read More
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.
Given a set $S$ of $m$ point sites in a simple polygon $P$ of $n$ vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for $S$ in $P$. It is known that the problem has an $Omega(n+mlog m)$ time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in $O(n+mlog m)$ expected time. The previous best deterministic algorithms solve the problem in $O(nlog log n+ mlog m)$ time [Oh, Barba, and Ahn, SoCG 2016] or in $O(n+mlog m+mlog^2 n)$ time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of $O(n+mlog m)$ time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.
We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector KDS handles each event in $O(log m)$ time, and our Voronoi center handles each event in $O(log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
Sampling, grouping, and aggregation are three important components in the multi-scale analysis of point clouds. In this paper, we present a novel data-driven sampler learning strategy for point-wise analysis tasks. Unlike the widely used sampling technique, Farthest Point Sampling (FPS), we propose to learn sampling and downstream applications jointly. Our key insight is that uniform sampling methods like FPS are not always optimal for different tasks: sampling more points around boundary areas can make the point-wise classification easier for segmentation. Towards the end, we propose a novel sampler learning strategy that learns sampling point displacement supervised by task-related ground truth information and can be trained jointly with the underlying tasks. We further demonstrate our methods in various point-wise analysis architectures, including semantic part segmentation, point cloud completion, and keypoint detection. Our experiments show that jointly learning of the sampler and task brings remarkable improvement over previous baseline methods.
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram $mathcal{V}(S)$ (and several variants thereof) of a set $S$ of $n$ sites in the plane as sites are added. We define a general update operation for planar graphs modeling the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in $mathbb{R}^3$. We show that the amortized number of edge insertions and removals needed to add a new site is $O(sqrt{n})$. A matching $Omega(sqrt{n})$ combinatorial lower bound is shown, even in the case where the graph of the diagram is a tree. This contrasts with the $O(log{n})$ upper bound of Aronov et al. (2006) for farthest-point Voronoi diagrams when the points are inserted in order along their convex hull. We present a semi-dynamic data structure that maintains the Voronoi diagram of a set $S$ of $n$ sites in convex position. This structure supports the insertion of a new site $p$ and finds the asymptotically minimal number $K$ of edge insertions and removals needed to obtain the diagram of $S cup {p}$ from the diagram of $S$, in time $O(K,mathrm{polylog} n)$ worst case, which is $O(sqrt{n};mathrm{polylog} n)$ amortized by the aforementioned result. The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained at all times and can be traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in $O(log n)$ time, or to determine whether two given sites are neighbors in the Delaunay triangulation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
