×

Conic nearest neighbor queries and approximate Voronoi diagrams. (English) Zbl 1315.65017

The paper deals with the conic nearest neighbour problem, i.e., given a cone \(C\) we want to preprocess a set \(S\) of \(n\) points in a Euclidean space so that for any query point \(q \in \mathbb R^d\) we can determine a nearest neighbour to \(q\) among points of \(S\) contained in cone \(C\) with apex at \(q\). The authors show how to construct an approximate conic Voronoi diagram of size \(O((n/\varepsilon^d)\log(1/\varepsilon))\) that can be used to answer approximate conic nearest neighbour queries in \(O(\log(n/\varepsilon))\), where \(\varepsilon > 0\) is a fixed approximation factor. The preprocessing time needed in the algorithm is \(O((n/\varepsilon^d)\log(n/\varepsilon)\log(1/\varepsilon))\).
In the algorithm, the cells of the approximate conic Voronoi diagram are first generated and stored in quadtree-like data structure. Then, each cell \(u\) is assigned an appropriate point \(p_u\) satisfying two requirements: (1) the distance from \(q \in u\) to \(p_u\) can be slightly larger than the distance from \(q\) to its exact conic nearest neighbour, (2) \(p_u\) lies either in the cone \(C\) or slightly outside of \(C\). To achieve this, the authors use the top-down method of propagation of representatives. After presenting the construction of the approximate conic Voronoi diagram, the authors show how the processing of queries is performed and prove its correctness. Moreover, they show that the fixed direction and fixed angle cone restriction can be easily removed with an increase in space by a factor of \(O(1/\varepsilon^d)\).

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65K05 Numerical mathematical programming methods
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Clarkson, K., A randomized algorithm for closest-point queries, SIAM J. Comput., 17, 830-847 (1988) · Zbl 0651.68062
[2] Meiser, S., Point location in arrangements of hyperplanes, Inf. Comput., 106, 286-303 (1993) · Zbl 0781.68121
[3] Arya, S.; Mount, D. M.; Netanyahu, N.; Silverman, R.; Wu, A. Y., An optimal algorithm for approximate nearest neighbor searching in fixed dimensions, J. Assoc. Comput. Mach., 45, 891-923 (1998) · Zbl 1065.68650
[4] Duncan, C. A.; Goodrich, M. T.; Kobourov, S., Balanced aspect ratio trees: combining the advantages of k-d trees and octrees, (Proc. of the 10th Annu. ACM-SIAM Sympos. Discrete Algorithms (1999)), 300-309 · Zbl 0934.68068
[5] Har-Peled, S., A replacement for Voronoi diagrams of near linear size, (Proc. of the 42nd Annu. IEEE Sympos. Found. Comput. Sci. (2001)), 94-103
[6] Arya, S.; Malamatos, T., Linear-size approximate Voronoi diagrams, (Proc. of the 13th Annu. ACM-SIAM Sympos. Discrete Algorithms (2002)), 147-155 · Zbl 1058.65019
[7] Arya, S.; Malamatos, T.; Mount, D. M., Space-time tradeoffs for approximate nearest neighbor searching, J. Assoc. Comput. Mach., 57, 1-54 (2009) · Zbl 1204.68103
[8] Arya, S.; Fonseca, G. D.; Mount, D. M., Approximate polytope membership queries, (Proc. of the 43rd Annu. ACM Sympos. Theory Comput. (2011)), 579-586 · Zbl 1288.68219
[9] Arya, S.; Fonseca, G. D.; Mount, D. M., Polytope approximation and the Mahler volume, (Proc. of the 23rd Annu. ACM-SIAM Sympos. Discrete Algorithms (2012)), 29-42 · Zbl 1422.68240
[10] Yao, A. C., On constructing minimum spanning trees in \(k\)-dimensional space and related problems, SIAM J. Comput., 11, 721-736 (1982) · Zbl 0492.68050
[11] Czumaj, A.; Ergün, F.; Fortnow, L.; Magen, A.; Newman, I.; Rubinfeld, R.; Sohler, C., Approximating the weight of the Euclidean minimum spanning tree in sublinear time, SIAM J. Comput., 35, 1, 91-109 (2005) · Zbl 1086.68144
[12] Arya, S.; Mount, D. M.; Smid, M., Dynamic algorithms for geometric spanners of small diameter: randomized solutions, Comput. Geom. Theory Appl., 13, 2, 91-107 (1999) · Zbl 0937.68137
[13] Clarkson, K., Approximation algorithms for shortest path motion planning, (Proc. of the 19th Annu. ACM Sympos. Theory Comput. (1987)), 56-65
[14] Agarwal, P. K.; Arge, L.; Erickson, J., Indexing moving points, J. Comput. Syst. Sci., 66, 207-243 (2003) · Zbl 1026.68143
[15] Funke, S.; Ramos, E. A., Smooth-surface reconstruction in near-linear time, (Proc. of the 13th Annu. ACM-SIAM Sympos. Discrete Algorithms (2002)), 781-790 · Zbl 1058.65026
[16] Dey, T. K.; Giesen, J.; Goswami, S.; Zhao, W., Shape dimension and approximation from samples, (Proc. of the 13th Annu. ACM-SIAM Sympos. Discrete Algorithms (2002)), 772-780 · Zbl 1058.65024
[17] Giesen, J.; Wagner, U., Shape dimension and intrinsic metric from samples of manifolds with high co-dimension, (Proc. of the 19th Annu. ACM Sympos. Comput. Geom. (2003)), 329-337 · Zbl 1375.68138
[18] Aronov, B.; Bose, P.; Demaine, E. D.; Gudmundsson, J.; Iacono, J.; Langerman, S.; Smid, M., Data structures for halfplane proximity queries and incremental Voronoi diagrams, (Proc. of the 7th Latin American Symposium on Theoretical Informatics (2006)), 80-92 · Zbl 1145.68554
[19] Narasimhan, G.; Smid, M., Geometric Spanner Networks (2007), Cambridge University Press · Zbl 1140.68068
[20] Callahan, P. B.; Kosaraju, S. R., Algorithms for dynamic closest pair and n-body potential fields, (Proc. of the 6th Annu. ACM-SIAM Sympos. Discrete Algorithms (1995)), 263-272 · Zbl 0849.68091
[21] Har-Peled, S., Geometric Approximation Algorithms (2011), American Mathematical Society · Zbl 1230.68215
[22] Samet, H., Foundations of Multidimensional and Metric Data Structures (2006), Morgan Kaufmann · Zbl 1139.68022
[23] Cormen, T. H.; Leiserson, C. E.; Rivers, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679
[24] Mount, D. M.; Park, E., A dynamic data structure for approximate range searching, (Proc. of the 26th Annu. ACM Sympos. Comput. Geom. (2010)), 247-256 · Zbl 1284.68216
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.