Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment
type: Item
instance of: scholarly article
title: Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment
zbMATH Open document ID: 1060.65026
author: Partha Goswami
author: Sandip Das
author: Subhas C. Nandy
published in: Computational Geometry
publication date: 2004-11-18T00:00:00Z
review text: The paper presents an algorithm to solve the following problem: given a set of \(n\) points arbitrarily distributed in the plane, find \(k\) nearest neighbors of a query line segment. First, an improved searching technique is developed for reporting the number of points that lie inside a query triangle. This counting query problem is solved in \(O(\log n)\) time with \(O(n^2)\) preprocessing time and space. Then the new triangular range searching technique leads to the solution of the \(k\)-nearest neighbors query in \(O(\log^2 n + k)\) time.
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 2116162
zbMATH Keywords: triangular range counting
zbMATH Keywords: segment dragging query
zbMATH Keywords: arrangement
zbMATH Keywords: duality
zbMATH Keywords: algorithm
reviewed by: Aurelian Bejancu
MaRDI profile type: Publication
full work available at URL: j.comgeo.2004.02.001
OpenAlex ID: W2000059698
cites work: Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
cites work: Q4225298
cites work: Dynamic half-space range reporting and its applications
cites work: COMPUTING CLOSEST POINTS FOR SEGMENTS
cites work: Queries with segments in Voronoi diagrams
cites work: Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
cites work: Cutting hyperplanes for divide-and-conquer
cites work: Fractional cascading. II: Applications
cites work: Quasi-optimal upper bounds for simplex range searching and new zone theorems
cites work: Searching and storing similar lists
cites work: Geometric retrieval problems
cites work: Q3772828
cites work: Halfplanar range search in linear space and \(O(n^{0.695})\) query time
cites work: The power of geometric duality revisited
cites work: Range searching with efficient hierarchical cuttings
cites work: Efficiently computing the closest point to a query line
cites work: An efficient \(k\) nearest neighbors searching algorithm for a query line.
DOI: 10.1016/J.COMGEO.2004.02.001
description: scientific article; zbMATH DE number 2116162