Efficient algorithms for bichromatic separability

ABSTRACT

A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding whether two sets of n points in ℝ³ can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double wedge. The latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.

REFERENCES

• 1: Agarwal, P. K., and Sharir, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B.V., North-Holland, Amsterdam, The Netherlands, pp. 49--119.
• 2: Pankaj K. Agarwal , Subhash Suri, Surface Approximation and Geometric Partitions, SIAM Journal on Computing, v.27 n.4, p.1016-1035, Aug. 1998 [doi>10.1137/S0097539794269801]
• 3: Arkin, E., Hurtado, F., Mitchell, J., Seara, C., and Skiena, S. 2001. Some lower bounds on geometric separability problems. In Proceedings of the 11th Fall Workshop on Computational Geometry.
• 4: Aronov, B., and Iacono, J. 2004. Detecting duplicates among similar bit vectors. In Proceedings of the 14th Fall Workshop on Computational Geometry.
• 5: Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
• 6: Boris Aronov , Micha Sharir , Boaz Tagansky, The Union of Convex Polyhedra in Three Dimensions, SIAM Journal on Computing, v.26 n.6, p.1670-1688, Dec. 1997 [doi>10.1137/S0097539793250755]
• 7: Boissonnat, J.-D., Czyzowicz, J., Devillers, O., Urrutia, J., and Yvinec, M. 2000. Computing largest circles separating two sets of segments. Internat. J. Comput. Geom. Appl. 10, 41--54.
• 8: Brönnimann, H., and Goodrich, M. T. 1995. Almost optimal set covers in finite VC-dimension. Disc. Comput. Geom. 14, 463--479.
• 9: de Berg, M., Dobrindt, K., and Schwarzkopf, O. 1995. On lazy randomized incremental construction. Disc. Comput. Geom. 14, 261--286.
• 10: David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
• 11: H. Edelsbrunner , F. P. Preparata, Minimum polygonal separation, Information and Computation, v.77 n.3, p.218-232, May 1988 [doi>10.1016/0890-5401(88)90049-1]
• 12: Eppstein, D. 1992. Dynamic three-dimensional linear programming. ORSA J. Comput. 4, 360--368.
• 13: Fekete, S. 1992. On the complexity of min-link red-blue separation. Unpublished manuscript.
• 14: Hastie, T., Tibshirani, R., and Friedman, J. 2001. The Elements of Statistical Learning. Springer-Verlag, Berlin, Germany.
• 15: Ferran Hurtado , Mercè Mora , Pedro A. Ramos , Carlos Seara, Separability by two lines and by nearly straight polygonal chains, Discrete Applied Mathematics, v.144 n.1-2, p.110-122, 30 November 2004 [doi>10.1016/j.dam.2003.11.014]
• 16: Ferran Hurtado , Marc Noy , Pedro A. Ramos , Carlos Seara, Separating objects in the plane by wedges and strips, Discrete Applied Mathematics, v.109 n.1-2, p.109-138, April 15, 2001 [doi>10.1016/S0166-218X(00)00230-4]
• 17: Hurtado, F., Seara, C., and Sethia, S. 2003. Red-blue separability problems in 3D. In Proceedings of the 3rd International Workshop on Computational Geometry and Applications.
• 18: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 19: Megiddo, N. 1983. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput. 12, 759--776.
• 20: Mitchell, J. S. B. 1993. Approximation algorithms for geometric separation problems. Tech. Rep. Dept. Applied Mathematics, SUNY Stony Brook, NY.
• 21: O'Rourke, J., Kosaraju, S. R., and Megiddo, N. 1986. Computing circular separability. Disc. Comput. Geom. 1, 105--113.
• 22: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Geometric algorithms, arrangements, separability