Kinetic k-semi-Yao graph and its applications

DOI10.1016/J.COMGEO.2015.11.001MaRDI QIDQ1622343zbMATH OpenOpenAlexFDO

Authors Zahed Rahmati, Mohammad A. Abam, Valerie King, Sue Whitesides

Publication date 19 November 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.5697

zbMATH Keywords

\(k\)-nearest neighborskinetic data structurecontinuous monitoringcontinuous queriesreverse \(k\)-nearest neighbor queries

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: This paper introduces a new proximity graph, called the $k$-Semi-Yao graph ($k$-SYG), on a set $P$ of points in $mathbb{R}^d$, which is a supergraph of the $k$-nearest neighbor graph ($k$-NNG) of $P$. We provide a kinetic data structure (KDS) to maintain the $k$-SYG on moving points, where the trajectory of each point is a polynomial function whose degree is bounded by some constant. Our technique gives the first KDS for the theta graph (ie, $1$-SYG) in $mathbb{R}^d$. It generalizes and improves on previous work on maintaining the theta graph in $mathbb{R}^2$. As an application, we use the kinetic $k$-SYG to provide the first KDS for maintenance of all the $k$-nearest neighbors in $mathbb{R}^d$, for any $kgeq1$. Previous works considered the $k=1$ case only. Our KDS for all the $1$-nearest neighbors is deterministic. The best previous KDS for all the $1$-nearest neighbors in $mathbb{R}^d$ is randomized. Our structure and analysis are simpler and improve on this work for the $k=1$ case. We also provide a KDS for all the $(1+epsilon)$-nearest neighbors, which in fact gives better performance than previous KDS's for maintenance of all the exact $1$-nearest neighbors. As another application, we present the first KDS for answering reverse $k$-nearest neighbor queries on moving points in $mathbb{R}^d$, for any $kgeq1$.

Recommendations

• A simple, faster method for kinetic proximity problems
• Approximate $k$-Nearest Neighbor Graph on Moving Points
• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic pie Delaunay graph and its applications

Cites work

• scientific article; zbMATH DE number 2185613 (Why is no real title available?)
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 3569833 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 6472653 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A simple, faster method for kinetic proximity problems
• Algorithms for proximity problems in higher dimensions
• An O(n log n) algorithm for the all-nearest-neighbors problem
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Computational geometry. Algorithms and applications.
• Euclidean minimum spanning trees and bichromatic closest pairs
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic reverse \(k\)-nearest neighbor problem
• Kinetic spanners in \(\mathbb R^{d}\)
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On \(k\)-sets in arrangements of curves and surfaces
• On levels in arrangements of curves, iii
• On levels in arrangements of curves. II: A simple inequality and its consequences
• On levels in arrangements of lines, segments, planes, and triangles
• Orthogonal range searching on the RAM, revisited
• REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION
• Sharp bounds on Davenport-Schinzel sequences of every order
• The complexity of selection and ranking in X+Y and matrices with sorted columns

Cited in

(3)

• Approximate $k$-Nearest Neighbor Graph on Moving Points
• A simple, faster method for kinetic proximity problems
• Kinetic pie Delaunay graph and its applications

This page was built for publication: Kinetic \(k\)-semi-Yao graph and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1622343)