No Access

SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS

Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA

E. Arkin and J. Mitchell acknowledge support from the National Science Foundation (CCR-0098172, CCF-0431030).

Dpt. Matemàtica Aplicada II, Univ. Politècnica de Catalunya, 08034 Barcelona, Spain

F. Hurtado and C. Seara acknowledge support from projects MCYT-FEDER BFM2002-0557, MCYT-FEDERBFM2003-0368, Gen-Cat 2001SGR00224 and 2005SGR00692.

Search for more papers by this author

JOSEPH S. B. MITCHELL

Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA

J. Mitchell acknowledges support from the U.S.-Israel Binational Science Foundation (Grant 2000160), Metron Aviation and NASA (NAG2-1325, NAG2-1620).

Search for more papers by this author

CARLOS SEARA

Dpt. Matemàtica Aplicada II, Univ. Politècnica de Catalunya, 08034 Barcelona, Spain

Search for more papers by this author

, and

STEVEN S. SKIENA

Computer Science, Stony Brook University, Stony Brook, NY 11794, USA

S. Skiena acknowledges support from NSF grants EIA-0325123 and DBI-0444815.

Search for more papers by this author

https://doi.org/10.1142/S0218195906001902Cited by:12 (Source: Crossref)

Abstract

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.

Partially supported by Joint Commission USA-Spain for Scientific and Technological Cooperation Project 98191.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

A. Aggarwalet al., Inform. Comput. 83, 98 (1989). Crossref, Web of Science, Google Scholar
E. M. Arkinet al., Some separability problems in the plane, Proc. 16th European Workshop on Computational Geometry (2000) pp. 51–54. Google Scholar
M. Ben-Or, Lower bounds for algebraic computation trees, Proc. 15th Ann. Symp. Theory of Computing (1983) pp. 80–86. Google Scholar
B. K. Bhathacharya , Computational Morphology , ed. G. T. Toussaint ( North Holland , 1988 ) . Google Scholar
J.-D. Boissonnatet al., Int. J. Comput. Geom. Appl. 10(1), 41 (2000). Link, Web of Science, Google Scholar
O. Devillerset al., Separating several point sets in the plane, Proc. 13th Canadian Conf. Computational Geometry (2001) pp. 81–84. Google Scholar
H. Edelsbrunner and F. P. Preparata, Inform. Comput. 77, 218 (1988). Crossref, Web of Science, Google Scholar
S. Fekete, On the complexity of min-link red-blue separation, manuscript, 1992 . Google Scholar
S. Fisk, IEEE Trans. Patt. Anal. Mach. Intell. 8(4), 554 (1986). Web of Science, Google Scholar
R. Freimer, Investigations in geometric subdivisions: Linear shattering and cartographic map coloring, Ph.D. Thesis, Computer Science, Cornell University, 2000 . Google Scholar
R. Freimer, J. S. B. Mitchell and C. D. Piatko, On the complexity of shattering using arrangements, Proc. 2nd Canadian Conf. Computational Geometry (1990) pp. 218–222. Google Scholar
F. Gómezet al., J. Math. Model. Algorith. 1, 57 (2002). Crossref, Google Scholar
M. E. Houle, Discr. Appl. Math. 45, 139 (1993). Crossref, Web of Science, Google Scholar
F. Hurtadoet al., Discr. Appl. Math. 109, 109 (2001). Crossref, Web of Science, Google Scholar
F. Hurtadoet al., Discr. Appl. Math. 144(1-2), 110 (2004). Crossref, Web of Science, Google Scholar
D. T. Lee and Y. F. Wu, Algorithmica 1, 193 (1986). Crossref, Web of Science, Google Scholar
N. Megiddo, SIAM J. Comput. 12(4), 759 (1983). Crossref, Web of Science, Google Scholar
J. O'Rourke, S. R. Kosaraju and N. Megiddo, Discr. Comput. Geom. 1(1), 105 (1986). Crossref, Web of Science, Google Scholar
P. Ramanan, Inform. Process. Lett. 24, 243 (1987). Crossref, Web of Science, Google Scholar
D. P. Wang and R. C. T. Lee, An optimal algorithm for solving the restricted minimal convex nested polygonal separation problem, Proc. 5th Canadian Conf. Computational Geometry (1993) pp. 334–339. Google Scholar