Abstract
In this paper we study the problems of separability of two disjoint point sets in 3D by multiple criteria extending some notions on separability of two disjoint point sets in the plane.
Partially supported by Proyectos DGES-MEC PB98-0933, UPC 1999SGR000356. Partially supported by Joint Commission USA-Spain for Scientific and Technological Cooperation Project 98191.
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.
References
E. M. Arkin, F. Hurtado, J. S. B. Mitchell, C. Seara, S. S. Skiena, Some Lower Bounds on Geometric Separability Problems, 11th Fall Workshop on Computational Geometry, 2001.
B. Aronov, M. Sharir, B. Tagansky The Union of Convex Polyhedral in Three Dimensions, SIAM J. Comput., Vol. 26, No. 6, 1997, pp. 1670–1688.
B. Chazelle, H. Edelsbrunner, An Optimal Algorithm for Intersecting Line Segments, Journal of ACM, 39, 1992, pp. 1–54.
G. Davis, Computing Separating Planes for a Pair of Disjoint Polytopes, Proceedings of the first Annual Symposium on Computational Geometry, 1985, pp. 8–14.
H. Edelsbrunner, F. P. Preparata, Minimum Polygonal Separation, Information and Computation, 77, 1988, pp. 218–232.
M. E. Houle, Algorithms for Weak and Wide Separation of Sets, Discrete Applied Mathematics, Vol. 45, 1993, pp. 139–159.
F. Hurtado, M. Noy, P. A. Ramos, C. Seara, Separating Objects in the Plane with Wedges and Strips, Discrete Applied Mathematics, Vol. 109, 2001, pp. 109–138.
F. Hurtado, M. Mora, P. A. Ramos, C. Seara, Two Problems on Separability with Lines and Polygonal, 15th European Workshop on Computational Geometry, 1999, pp. 33–35.
G. O. Katona, On a Problem of L. Fejes Tth, Stud. Sci. Math. Hung., 12, 1977, pp. 77–80.
N. Megiddo, Linear-time Algorithms for Linear Programming in ℝ 3 and Related Problems, SIAM J. Computer, Vol. 12, No. 4, 1983, pp. 759–776.
F. P. Preparata, S. J. Hong, Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Communications of the ACM, 20, 1977, pp. 87–93.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hurtado, F., Seara, C., Sethia, S. (2003). Red-Blue Separability Problems in 3D. In: Kumar, V., Gavrilova, M.L., Tan, C.J.K., L’Ecuyer, P. (eds) Computational Science and Its Applications — ICCSA 2003. ICCSA 2003. Lecture Notes in Computer Science, vol 2669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44842-X_78
Download citation
DOI: https://doi.org/10.1007/3-540-44842-X_78
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40156-8
Online ISBN: 978-3-540-44842-6
eBook Packages: Springer Book Archive