Abstract
In this paper, we study a kinetic version of the red-blue minimum separating circle problem, in which some points move with constant speed along straight line trajectories. We want to find the locus of the minimum separating circle over a period of time. We first consider two degenerate cases of this problem. In the first one (P1), we study the minimum separating circle problem with only one mobile blue point, and in the second one (P2), we study the minimum separating circle problem with only one mobile red point. Then, we give a solution for the general case (P3), in which multiple points are mobile.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albers, G., Guibas, L.J., Mitchell, J.S.B., Roos, T.: Voronoi diagrams of moving points. Int. J. Comput. Geometry Appl. 8(3), 365–380 (1998)
Aronov, B., Rappaport, D., Seara, C., Garijo, D., Núñez, Y., Urrutia, J.: Measuring the error of linear separators on linearly inseparable data. In: XIII Encuentros de Geometria Computacional, Zaragoza, España (2009)
Atallah, M.J.: Dynamic computational geometry (preliminary version). In: FOCS, pp. 92–99 (1983)
Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. J. Algorithms 31(1), 1–28 (1999)
Basch, J., Guibas, L.J., Silverstein, C., Zhang, L.: A practical evaluation of kinetic data structures. In: Symposium on Computational Geometry, pp. 388–390 (1997)
Bitner, S., Cheung, Y.K., Daescu, O.: Minimum separating circle for bichromatic points in the plane. In: ISVD, pp. 50–55 (2010)
Demain, E., Einsenstat, S., Guibas, L., Schulz, A.: Kinetic minimum spanning circle. In: Proceedings of the Fall Workshop on Computational Geometry, New York, USA (2010)
Mitchell, J.S.B., Seara, C., Arkin, E.M., Hurtado, F., Skiena, S.: Some lower bounds on geometric separability problems. Int. J. Comput. Geometry Appl. 16(1), 1–26 (2006)
Seara, C., Hurtado, F., Sethia, S.: Red-blue separability problems in 3d. International Journal of Computational Geometry 15(2), 167–192 (2005)
Fekete, S.: On the complexity of min-link red-blue separation (1992) (manuscript)
Fisk, S.: Separating point sets by circles, and the recognition of digital disks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 554–556 (July 1986)
Guibas, L.J.: Kinetic data structures: a state of the art report. In: WAFR 1998 (1998)
Hurtado, F., Mora, M., Ramos, P.A., Seara, C.: Separability by two lines and by nearly straight polygonal chains. Discrete Applied Mathematics 144(1-2), 110–122 (2004)
Hurtado, F., Noy, M., Ramos, P.A., Seara, C.: Separating objects in the plane by wedges and strips. Discrete Applied Mathematics 109(1-2), 109–138 (2001)
Megiddo, N.: Linear-time algorithms for linear programming in R 3 and related problems. SIAM Journal on Computing 12(4), 759–776 (1983)
O’Rourke, J., Kosaraju, S., Megiddo, N.: Computing circular separability. Discrete Computational Geometry 1, 105–113 (1986)
Rahmati, Z., Zarei, A.: Combinatorial changes of euclidean minimum spanning tree of moving points in the plane. In: CCCG, pp. 43–45 (2010)
Roos, T.: Voronoi diagrams over dynamic scenes. Discrete Applied Mathematics 43(3), 243–259 (1993)
Skyum, S.: A simple algorithm for computing the smallest enclosing circle. Information Processing Letters 37(3) (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cheung, Y.K., Daescu, O., Zivanic, M. (2011). Kinetic Red-Blue Minimum Separating Circle. In: Wang, W., Zhu, X., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2011. Lecture Notes in Computer Science, vol 6831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22616-8_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-22616-8_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22615-1
Online ISBN: 978-3-642-22616-8
eBook Packages: Computer ScienceComputer Science (R0)