SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
Esther M. Arkin, Ferrán Hurtado, Joseph S. B. Mitchell, Carlos Seara, Steven Skiena · International Journal of Computational Geometry & Applications · 2006
We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(n log n) time lower bounds for separability by means of strips, wedges, wedges with apices on a given line, fixed-slopes double wedges, and triangles, which match the complexity of the existing algorithms, and therefore prove their optimality.