No Access

OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE

MARK DE BERG

Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, P. O. Box 513, 5600 MB, The Netherlands

Search for more papers by this author

and

AMIRALI KHOSRAVI

Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, P. O. Box 513, 5600 MB, The Netherlands

Search for more papers by this author

https://doi.org/10.1142/S0218195912500045Cited by:67 (Source: Crossref)

Abstract

An optimal BSP for a set S of disjoint line segments in the plane is a BSP for S that produces the minimum number of cuts. We study optimal BSPs for three classes of BSPs, which differ in the splitting lines that can be used when partitioning a set of fragments in the recursive partitioning process: free BSPs can use any splitting line, restricted BSPs can only use splitting lines through pairs of fragment endpoints, and auto-partitions can only use splitting lines containing a fragment. We obtain the following two results:

• It is NP-hard to decide whether a given set of segments admits an auto-partition that does not make any cuts.

• An optimal restricted BSP makes at most 2 times as many cuts as an optimal free BSP for the same set of segments.

This research was supported by the Netherlands' Organisation for Scientific Research (NWO) under project no. 639.023.301.

Keywords:

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

References

F. d'Amore and P. G. Franciosa, Infor. Process. Lett. 44, 255 (1992), DOI: 10.1016/0020-0190(92)90210-M. Web of Science, Google Scholar
F. d'Amoreet al., Computing 55, 191 (1995), DOI: 10.1007/BF02238431. Web of Science, Google Scholar
M. de Berg, M. M. de Groot and M. H. Overmars, Comput. Geom. Theor. Appl. 7, 81 (1997), DOI: 10.1016/0925-7721(95)00045-3. Web of Science, Google Scholar
M. de Berg, E. Mumford and B. Speckmann, Int. J. Comput. Geom. Appl. 20, 203 (2006), DOI: 10.1142/S0218195910003268. Link, Web of Science, Google Scholar
M. de Berg, Algorithmica 28, 353 (2000), DOI: 10.1007/s004530010047. Web of Science, Google Scholar
M. de Berg et al. , Computational Geometry: Algorithms and Applications ( Springer Verlag , Berlin , 2008 ) . Google Scholar
X. Clairbois, On optimal binary space partitions, MSc. thesis, Eindhoven University of Technology (2006) . Google Scholar
M. R. Garey and D. S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness ( W.H. Freeman and Co. , New York , 1979 ) . Google Scholar
B. Katz, I. Rutter and G. Woeginger, An algorithmic study of switch graphs, Proc. 35th Int. Workshop on Graph-Theoretic Concepts in Computer Science5911, LNCS (2010) pp. 226–237. Google Scholar
D. E. Knuth and A. Raghunathan, SIAM J. Discr. Math. 5, 422 (1992), DOI: 10.1137/0405033. Web of Science, Google Scholar
D. Lichtenstein, SIAM J. Comput. 11, 329 (1982), DOI: 10.1137/0211025. Web of Science, Google Scholar
M. S. Paterson and F. F. Yao, Discr. Comput. Geom. 5, 485 (1990), DOI: 10.1007/BF02187806. Web of Science, Google Scholar
M. S. Paterson and F. F. Yao, J. Alg. 13, 99 (1992). Web of Science, Google Scholar
C. D. Tóth, Discr. Comput. Geom. 30, 3 (2003). Web of Science, Google Scholar
C. D. Tóth, Combinat. Comput. Geom. 52, 525 (2005). Google Scholar
C. D. Tóth, Discr. Comput. Geom. 45, 617 (2011). Web of Science, Google Scholar