{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:34:45Z","timestamp":1759847685649},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p> A cartogram is a thematic map that visualizes statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic variable, for example, population. We present an algorithm for constructing rectilinear cartograms (each region is represented by a rectilinear polygon) with zero cartographic error and correct region adjacencies, and we test our algorithm on various data sets. It produces regions of very small complexity\u2014in fact, most regions are rectangles\u2014while still ensuring both exact areas and correct adjacencies for all regions. <\/jats:p><jats:p> Our algorithm uses a novel subroutine that is interesting in its own right, namely a polynomial-time algorithm for computing optimal binary space partitions (BSPs) for rectilinear maps. This algorithm works for a general class of optimality criteria, including size and depth. We use this generality in our application to computing cartograms, where we apply a dedicated cost function leading to BSPs amenable to the constructing of high-quality cartograms. <\/jats:p>","DOI":"10.1142\/s0218195910003268","type":"journal-article","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T11:38:07Z","timestamp":1271849887000},"page":"203-222","source":"Crossref","is-referenced-by-count":19,"title":["OPTIMAL BSPs AND RECTILINEAR CARTOGRAMS"],"prefix":"10.1142","volume":"20","author":[{"given":"MARK","family":"DE BERG","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computing Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ELENA","family":"MUMFORD","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computing Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BETTINA","family":"SPECKMANN","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computing Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","first-page":"307","volume":"7","author":"Bhasker J.","journal-title":"Networks"},{"key":"rf2","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2001"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90210-M"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.087"},{"key":"rf6","volume-title":"Cartography: Thematic Map Design","author":"Dent B.","year":"1999"},{"key":"rf7","volume-title":"Area Cartograms: their Use and Creation","author":"Dorling D.","year":"1996"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1111\/j.0033-0124.1985.00075.x"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00006-5"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400280101"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(95)00257-X"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.1260761"},{"key":"rf15","first-page":"145","volume":"5","author":"Ko\u0144mi\u0144ski K.","journal-title":"Networks"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1111\/j.0033-0124.1976.00371.x"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.2307\/208794"},{"key":"rf18","volume-title":"The Design and Analysis of Spatial Data Structures","author":"Samet H.","year":"1989"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1559\/152304086783900194"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63818-0"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.06.002"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195910003268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:21:16Z","timestamp":1565094076000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195910003268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":18,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1142\/S0218195910003268"],"URL":"https:\/\/doi.org\/10.1142\/s0218195910003268","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4]]}}}