Localized geometric query problems

A. Aggarwal, L.J. Guibas, J. Saxe, P.W. Shor, A linear time algorithm for computing the Voronoi diagram of a convex polygon, in: Proc. of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 39–45. Augustine, 2010, Largest empty circle centered on a query line, Journal of Discrete Algorithms, 8, 143, 10.1016/j.jda.2009.10.002 Augustine Bender, 2004, The level ancestor problem simplified, Theoretical Computer Science, 321, 5, 10.1016/j.tcs.2003.05.002 Boissonnat, 2000, Computing largest circles separating two sets of segments, International Journal of Computational Geometry and Applications, 10, 41, 10.1142/S0218195900000036 Boissonnat, 2001, Circular separability of polygons, Algorithmica, 30, 67, 10.1007/s004530010078 Chin, 1999, Finding the medial axis of a simple polygon in linear time, Discrete Computational Geometry, 21, 405, 10.1007/PL00009429 Edmonds, 2003, Mining for empty spaces in large data sets, Theoretical Computer Science, 296, 435, 10.1016/S0304-3975(02)00738-7 Fisk, 1986, Separating point sets by circles, and the recognition of digital disks, Transactions on Pattern Analysis and Machine Intelligence, 8, 554, 10.1109/TPAMI.1986.4767821 Frederickson, 1987, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, 16, 1004, 10.1137/0216064 Imai, 1985, Voronoi diagram in the Laguerre geometry and its applications, SIAM Journal on Computing, 14, 93, 10.1137/0214006 Jordan, 1869, Sur les assemblages de lignes, Journal fur die Reine und Angewandte Mathematik, 70, 185, 10.1515/crll.1869.70.185 H. Kaplan, S. Mozes, Y. Nussbaum, M. Sharir, Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications, in: Proceedings of the Symposium on Discrete Algorithms, 2012, pp. 338–355. H. Kaplan, M. Sharir, Finding the maximal empty disk containing a query point, in: Proceedings of the Symposium on Computational Geometry, 2012, pp. 287–292. Kirkpatrick, 1983, Optimal search in planar subdivisions, SIAM Journal on Computing, 12, 28, 10.1137/0212002 Lipton, 1979, A separator theorem for planar graphs, SIAM Journal on Applied Mathematics, 36, 177, 10.1137/0136016 B. Liu, L. Ku, W. Hsu, Discovering interesting holes in data, in: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, 1997, pp. 930–935. OʼRourke, 1986, Computing circular separability, Discrete & Computational Geometry, 1, 105, 10.1007/BF02187688 F.P. Preparata, The medial axis of a simple polygon, in: Mathematical Foundations of Computer Science, 1977, pp. 443–450. Toussaint, 1983, Computing largest empty circles with location constraints, International Journal of Parallel Programming, 12, 347