{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T10:43:22Z","timestamp":1749725002768},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1999,2]]},"abstract":"<jats:p> Let S be a set of n points in the plane. We study the following problem: Partition S by a line into two subsets S<jats:sub>a<\/jats:sub> and S<jats:sub>b<\/jats:sub> such that max{f(S<jats:sub>a<\/jats:sub>), f(S<jats:sub>b<\/jats:sub>)} is minimal, where f is any monotone function defined over 2<jats:sup>S<\/jats:sup>. We first present a solution to the case where the points in S are the vertices of a convex polygon and apply it to some common cases \u2014 f(S\u2032) is the perimeter, area, or width of the convex hull of S\u2032\u2286S \u2014 to obtain linear solutions (or O(n log \u00a0n) solutions if the convex hull of S is not given) to the corresponding problems. This solution is based on an efficient procedure for finding a minimal entry in matrices of some special type, which we believe is of independent interest. For the general case we present a linear space solution which is in some sense output sensitive. It yields solutions to the perimeter and area cases that are never slower and often faster than the best previous solutions. <\/jats:p>","DOI":"10.1142\/s0218195999000042","type":"journal-article","created":{"date-parts":[[2003,5,22]],"date-time":"2003-05-22T02:35:01Z","timestamp":1053570901000},"page":"39-51","source":"Crossref","is-referenced-by-count":6,"title":["OPTIMAL LINE BIPARTITIONS OF POINT SETS"],"prefix":"10.1142","volume":"09","author":[{"given":"OLIVIER","family":"DEVILLERS","sequence":"first","affiliation":[{"name":"INRIA, B.P.\u00a093, 06902 Sophia-Antipolis cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATTHEW J.","family":"KATZ","sequence":"additional","affiliation":[{"name":"Departments of Industrial Engineering &amp; Management and Mathematics &amp; Computer Science,  Ben-Gurion University of the Negev, Beer-Sheva\u00a084105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182774"},{"key":"p_2","first-page":"252","author":"Asano Te.","year":"1988","journal-title":"Proc. 4th Annu. ACM Sympos. Gomput. Geom., pages"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187699"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90009-U"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90013-O"},{"key":"p_10","first-page":"303","author":"Jaromczyk J. W.","year":"1994","journal-title":"Proc. 10th Annu. ACM Sympos. Comput. Geom., pages"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377043"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161137"},{"key":"p_14","first-page":"899","volume":"2","author":"Monma C.","year":"1991","journal-title":"Graph Theory, Combinatorics and Applications (Proc. 6th Internat. Conf. Theory Appl. Graphs)"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"p_17","first-page":"11","author":"Rokne J.","year":"1992","journal-title":"Proc. 4th Canad. Conf. Comput. Geom., pages"},{"key":"p_18","first-page":"106","author":"Sharir M.","year":"1996","journal-title":"Proc. 12th Annu. ACM Sympos. Comput. Geom., pages"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195999000042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:32:02Z","timestamp":1565123522000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195999000042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,2]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1999,2]]}},"alternative-id":["10.1142\/S0218195999000042"],"URL":"https:\/\/doi.org\/10.1142\/s0218195999000042","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,2]]}}}