{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T08:33:38Z","timestamp":1697186018232},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1993,12]]},"abstract":"<jats:p> Let P be a set of n points located inside a d-box (rectangle if d=2) R. We study the problem of partitioning R into d-boxes by introducing a set of hyperplane (line if d=2) segments of least total (d-1)\u2013volume (length if d=2). Each of the resulting d-boxes in a valid partition cannot contain points from P as interior points. Since this problem is computationally intractable (NP-hard) even when d=2, we present an efficient approximation algorithm for its solution. The partition generated by our approximation algorithm is guaranteed to be within 2d times the optimal solution value. We also present a problem instance for each d\u22652 for which the approximation bound is tight for the algorithm. The time complexity for our algorithm is O(dn log n). <\/jats:p>","DOI":"10.1142\/s0218195993000269","type":"journal-article","created":{"date-parts":[[2004,11,22]],"date-time":"2004-11-22T22:29:30Z","timestamp":1101162570000},"page":"417-428","source":"Crossref","is-referenced-by-count":5,"title":["AN EFFICIENT DIVIDE-AND-CONQUER APPROXIMATION ALGORITHM FOR PARTITIONING INTO D-BOXES"],"prefix":"10.1142","volume":"03","author":[{"given":"TEOFILO F.","family":"GONZALEZ","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, California 93106\u20135110, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MOHAMMADREZA","family":"RAZZAZI","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, California 93106\u20135110, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SI-QING","family":"ZHENG","sequence":"additional","affiliation":[{"name":"Computer Science Department, Louisiana State University, Baton Rouge, Louisiana 70803\u20134020, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195993000269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:36:41Z","timestamp":1565177801000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195993000269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":0,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,12]]}},"alternative-id":["10.1142\/S0218195993000269"],"URL":"https:\/\/doi.org\/10.1142\/s0218195993000269","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}