{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:52:00Z","timestamp":1780822320185,"version":"3.54.1"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p> 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: <\/jats:p><jats:p> \u2022 It is NP-hard to decide whether a given set of segments admits an auto-partition that does not make any cuts. <\/jats:p><jats:p> \u2022 An optimal restricted BSP makes at most 2 times as many cuts as an optimal free BSP for the same set of segments. <\/jats:p>","DOI":"10.1142\/s0218195912500045","type":"journal-article","created":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T07:30:09Z","timestamp":1350372609000},"page":"187-205","source":"Crossref","is-referenced-by-count":75,"title":["OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE"],"prefix":"10.1142","volume":"22","author":[{"given":"MARK","family":"DE BERG","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, P. O. Box 513, 5600 MB, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"AMIRALI","family":"KHOSRAVI","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, P. O. Box 513, 5600 MB, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2012,10,16]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90210-M"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238431"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00045-3"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195910003268"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010047"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"rf8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/0405033"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187806"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90007-Y"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2921-x"},{"key":"rf15","first-page":"525","volume":"52","author":"T\u00f3th C. D.","journal-title":"Combinat. Comput. Geom."},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9341-0"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195912500045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:21:06Z","timestamp":1565097666000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195912500045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":14,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,10,16]]},"published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1142\/S0218195912500045"],"URL":"https:\/\/doi.org\/10.1142\/s0218195912500045","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}