×

Largest empty circle centered on a query line. (English) Zbl 1186.90068

Summary: The Largest Empty Circle problem seeks the largest circle centered within the convex hull of a set \(P\) of \(n\) points in \(\mathbb R^2\) and devoid of points from \(P\). In this paper, we introduce a query version of this well-studied problem. In our query version, we are required to preprocess \(P\) so that when given a query line \(Q\), we can quickly compute the largest empty circle centered at some point on \(Q\) and within the convex hull of \(P\).We present solutions for two special cases and the general case; all our queries run in \(O(\log n)\) time. We restrict the query line to be horizontal in the first special case, which we preprocess in \(O(n\alpha (n) \log n)\) time and space, where \(\alpha (n)\) is the slow growing inverse of Ackermann’s function. When the query line is restricted to pass through a fixed point, the second special case, our preprocessing takes \(O(n\alpha (n)^{O(\alpha (n))}\log n)\) time and space. We use insights from the two special cases to solve the general version of the problem with preprocessing time and space in \(O(n^3\log n)\) and \(O(n^{3})\) respectively.

MSC:

90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bern, M. W.; Dobkin, D. P.; Eppstein, D.; Grossman, R. L., Visibility with a moving point of view, Algorithmica, 11, 360-378 (1994) · Zbl 0804.68147
[2] Bose, P.; Langerman, S.; Roy, S., Smallest enclosing circle centered on a query line segment, (Proc. of the Canadian Conference on Computational Geometry (2008)), 167-170
[3] Bose, P.; Wang, Q., Facility location constrained to a polygonal domain, (Proc. of the Latin American Theoretical Informatics Symposium (2002)), 153-164 · Zbl 1059.90516
[4] P. Cappanera, A survey on obnoxious facility location problems, Technical Report TR-99-11, Universita Di Pisa, 1999; P. Cappanera, A survey on obnoxious facility location problems, Technical Report TR-99-11, Universita Di Pisa, 1999
[5] L.P. Chew, R.L.S. Drysdale, Finding largest empty circles with location constraints, Technical Report PCS-TR86-130, Dartmouth College, 1986; L.P. Chew, R.L.S. Drysdale, Finding largest empty circles with location constraints, Technical Report PCS-TR86-130, Dartmouth College, 1986
[6] Davenport, H.; Schinzel, A., A combinatorial problem connected with differential equations, American Journal of Mathematics, 87, 684-694 (1965) · Zbl 0132.00601
[7] Dickerson, M.; Scharstein, D., Optimal placement of convex polygons to maximize point containment, Computational Geometry, 11, 1, 1-16 (1998) · Zbl 0904.68175
[8] Driscoll, J. R.; Sarnak, N.; Sleator, D. D.; Tarjan, R. E., Making data structures persistent, Journal of Computer and System Sciences, 38, 684-694 (1989) · Zbl 0667.68026
[9] Hershberger, J., Finding the upper envelope of \(n\) line segments in \(o(n \log n)\) time, Information Processing Letters, 33, 169-174 (1989) · Zbl 0689.68058
[10] Knuth, D., The Art of Computer Programming, Vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley New York, USA · Zbl 0302.68010
[11] Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer-Verlag: Springer-Verlag New York, USA · Zbl 0759.68037
[12] Sharir, M.; Agarwal, P. K., Davenport-Schinzel Sequences and Their Geometric Applications (1996), Cambridge University Press: Cambridge University Press New York, USA · Zbl 0952.68148
[13] Toussaint, G., Computing largest empty circles with location constraints, International Journal of Parallel Programming, 12, 347-358 (1983) · Zbl 0525.90039
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.