Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment

Agarwal, 1998, Constructing levels in arrangement and higher order Voronoi diagram, SIAM J. Comput, 27, 654, 10.1137/S0097539795281840 Agarwal, 1996, Geometric range searching and its relatives, Advances in Discrete and Computational Geometry, vol. 223, 1 Agarwal, 1995, Dynamic half-space range reporting and its applications, Algorithmica, 13, 325, 10.1007/BF01293483 Bespamyatnikh, 2003, Computing closest points for segments, Internat. J. Comput. Geom. Appl, 13, 419, 10.1142/S0218195903001268 Bespamyatnikh, 2000, Queries with segments in Voronoi diagram, Computational Geometry, 16, 23, 10.1016/S0925-7721(99)00055-3 Chan, 2000, Random sampling, halfspace range reporting, and construction of (⩽k)-levels in three dimension, SIAM J. Comput, 30, 561, 10.1137/S0097539798349188 Chazelle, 1993, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom, 9, 145, 10.1007/BF02189314 Chazelle, 1986, Fractional cascading—II. Applications, Algorithmica, 1, 163, 10.1007/BF01840441 Chazelle, 1992, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Algorithmica, 8, 407, 10.1007/BF01758854 Cole, 1986, Searching and storing similar lists, J. Algorithms, 7, 202, 10.1016/0196-6774(86)90004-0 Cole, 1984, Geometric retrieval problems, Inform. and Control, 63, 39, 10.1016/S0019-9958(84)80040-6 Edelsbrunner, 1987 Edelsbrunner, 1986, Halfplanar range search in linear space and O(n.695) query time, Inform. Process. Lett, 23, 289, 10.1016/0020-0190(86)90088-8 Lee, 1985, The power of geometric duality revisited, Inform. Process. Lett, 21, 117, 10.1016/0020-0190(85)90015-8 Matousek, 1993, Range searching with efficient hierarchical cutting, Discrete Comput. Geom, 10, 157, 10.1007/BF02573972 Mitra, 1998, Efficiently computing the closest point to a query line, Pattern Recogn. Lett, 19, 1027, 10.1016/S0167-8655(98)00080-4 Mukhopadhyay, 2002, Using simplicial partitions to determine a closest point to a query line, 10 Nandy, 2003, An efficient k-nearest neighbors searching algorithm for a query line, Theoret. Comput. Sci, 299, 273, 10.1016/S0304-3975(02)00322-5