{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T06:31:20Z","timestamp":1742970680058,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":15,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_2","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:52Z","timestamp":1461269032000},"page":"18-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Adaptive Partitions"],"prefix":"10.1007","author":[{"given":"Ping","family":"Deng","sequence":"first","affiliation":[]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Eugene","family":"Shragowitz","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"1_CR160","doi-asserted-by":"crossref","unstructured":"Arora S (1996) Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 37th IEEE symposium on foundations of computer science, pp\u00a02\u201312","DOI":"10.1109\/SFCS.1996.548458"},{"key":"1_CR161","doi-asserted-by":"crossref","unstructured":"Arora S (1997) Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 38th IEEE symposium on foundations of computer science, pp\u00a0554\u2013563","DOI":"10.1109\/SFCS.1997.646145"},{"key":"1_CR162","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S (1998) Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J ACM 45:753\u2013782","journal-title":"J ACM"},{"key":"1_CR163","unstructured":"Du D-Z, Pan, L-Q, Shing, M-T (1986) Minimum edge length guillotine rectangular partition. Technical report 0241886, Math. Sci. Res. Inst., Univ. California, Berkeley"},{"key":"1_CR164","first-page":"313","volume":"58","author":"D-Z Du","year":"1987","unstructured":"Du D-Z, Hsu DF, Xu K-J (1987) Bounds on guillotine ratio. Congressus Numerantium 58:313\u2013318","journal-title":"Congressus Numerantium"},{"key":"1_CR165","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1109\/31.7610","volume":"35","author":"DZ Du","year":"1988","unstructured":"Du DZ, Hwang FK, Shing MT, Witbold T (1988) Optimal routing trees. IEEE Trans Circuits 35:1335\u20131337","journal-title":"IEEE Trans Circuits"},{"key":"1_CR166","doi-asserted-by":"crossref","unstructured":"Gonzalez T, Zheng SQ (1985) Bounds for partitioning rectilinear polygons. In: Proceedings of the 1st symposium on computational geometry","DOI":"10.1145\/323233.323269"},{"key":"1_CR167","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1016\/S0747-7171(89)80042-2","volume":"7","author":"T Gonzalez","year":"1989","unstructured":"Gonzalez T, Zheng SQ (1989) Improved bounds for rectangular and guillotine partitions. J Symb Comput 7:591\u2013610","journal-title":"J Symb Comput"},{"key":"1_CR168","unstructured":"Lingas A (1983) Heuristics for minimum edge length rectangular partitions of rectilinear figures. In: Proceedings of the 6th GI-conference, Dortmund. Springer"},{"key":"1_CR169","unstructured":"Lingas A, Pinter RY, Rivest RL, Shamir A (1982) Minimum edge length partitioning of rectilinear polygons. In: Proceedings of the 20th Allerton conference on communication, control, and computing, Illinois"},{"key":"1_CR170","first-page":"155","volume":"37","author":"M Min","year":"2003","unstructured":"Min M, Huang SC-H, Liu J, Shragowitz E, Wu W, Zhao Y, Zhao Y (2003) An approximation scheme for the rectilinear Steiner minimum tree in presence of obstructions. Fields Inst Commun 37:155\u2013164","journal-title":"Fields Inst Commun"},{"key":"1_CR171","unstructured":"Mitchell JSB (1996) Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem. In: Proceedings of the 7th ACM-SIAM symposium on discrete algorithms, pp\u00a0402\u2013408"},{"key":"1_CR172","volume-title":"Guillotine subdivisions approximate polygonal subdivisions: part III \u2013 faster polynomial-time approximation scheme for geometric network optimization, manuscript","author":"JSB Mitchell","year":"1997","unstructured":"Mitchell JSB (1997) Guillotine subdivisions approximate polygonal subdivisions: part III \u2013 faster polynomial-time approximation scheme for geometric network optimization, manuscript, State University of New York, Stony Brook"},{"issue":"2","key":"1_CR173","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1137\/S0097539797320281","volume":"29","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell JSB (1999) Guillotine subdivisions approximate polygonal subdivisions: part II \u2013 a simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problem. SIAM J Comput 29(2):515\u2013544","journal-title":"SIAM J Comput"},{"issue":"3","key":"1_CR174","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1137\/S0097539796303299","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell JSB, Blum A, Chalasani P, Vempala S (1999) A constant-factor approximation algorithm for the geometric k-MST problem in the plane. SIAM J Comput 28(3):771\u2013781","journal-title":"SIAM J Comput"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:09:50Z","timestamp":1553098190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_2","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}