{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:51:07Z","timestamp":1774626667981,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602200","type":"print"},{"value":"9783540447474","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_64","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:52:38Z","timestamp":1330278758000},"page":"218-227","source":"Crossref","is-referenced-by-count":8,"title":["Quadrangulations of planar sets"],"prefix":"10.1007","author":[{"given":"Godfried","family":"Toussaint","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"issue":"2","key":"19_CR1","first-page":"290","volume":"33","author":"T. Asano","year":"1986","unstructured":"Takao Asano, Tetsuo Asano and H. Imai, \u201cPartitioning a polygonal region into trapezoids,\u201d Journal of the A.C.M., vol. 33, No. 2, April 1986, pp. 290\u2013312.","journal-title":"Journal of the A.C.M."},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Arkin, E., M. Held, J. Mitchell, and S. Skiena, \u201cHamiltonian triangulations for fast rendering,\u201d Algorithms-ESA'94, J. van Leeuwen, ed., Utrecht, NL, LNCS 855, pp. 36\u201347, September 1994.","DOI":"10.1007\/BFb0049395"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Bern, M. and Eppstein, D., \u201cMesh generation and optimal triangulation,\u201d in Computing in Euclidean Geometry, F. K. Hwang and D.-Z. Du, eds., World Scientific 1992.","DOI":"10.1142\/9789814355858_0002"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1006\/jagm.1994.1040","volume":"17","author":"H. Baumgarten","year":"1994","unstructured":"Baumgarten, H., Jung, H. and Mehlhorn, K., \u201cDynamic point location in general subdivisions,\u201d Journal of Algorithms, vol. 17, 1994, pp. 342\u2013380.","journal-title":"Journal of Algorithms"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Barequet, G., and M. Sharir, \u201cPiecewise-linear interpolation between polygonal slices,\u201d Proceedings of the 10th Annual Symposium on Computational Geometry, pp. 93\u2013102, 1994.","DOI":"10.1145\/177424.177562"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Bose, P., and G. Toussaint, \u201cNo Quadrangulation is Extremely Odd,\u201d technical report #95-03, Dept. of Computer Science, University of British Columbia, January 1995.","DOI":"10.1007\/BFb0015443"},{"key":"19_CR7","unstructured":"P. Bose and G. T. Toussaint, \u201cOn computing quadrangulations of planar point sets,\u201d 10th Colloquium on Graph Theory, Combinatorics and Applications, Feb. 27\u2013March 3, 1995, Xalapa, Mexico."},{"key":"19_CR8","unstructured":"P. Bose and G. T. Toussaint, \u201cGenerating quadrangulations of planar point sets,\u201d accepted for publication in Computer Aided Geometric Design."},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"31","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B., \u201cOn the convex layers of a convex set,\u201d IEEE Transactions on Information Theory, vol. IT-31, 1985, pp. 509\u2013517.","journal-title":"IEEE Transactions on Information Theory"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle, \u201cTriangulating a simple polygon in linear time,\u201d Discrete Comput. Geom., vol. 6, 1991, pp. 485\u2013524.","journal-title":"Discrete Comput. Geom."},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V. Chv\u00e1tal","year":"1975","unstructured":"V. Chv\u00e1tal, \u201cA combinatorial theorem in plane geometry,\u201d J. Combin. Theory Ser. B, vol. 18, 1975, pp. 39\u201341.","journal-title":"J. Combin. Theory Ser. B"},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/0221057","volume":"21","author":"S. W. Cheng","year":"1992","unstructured":"Cheng, S. W. and Janardan, R., \u201cNew results on dynamic planar point location,\u201d SIAM Journal on Computing, vol. 21, 1992, pp. 972\u2013999.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR13","unstructured":"H. E. Conn and J. O'Rourke, \u201cMinimum weight quadrilateralization in O(n3 log n) time,\u201d Proc. of the 28th Allerton Conference on Comm. Control and Computing, October 1990, pp. 788\u2013797."},{"key":"19_CR14","unstructured":"Everett, H., W. Lenhart, M. Overmars, T. Shermer, and J. Urrutia, \u201cStrictly convex quadrilateralizations of polygons,\u201d in Proceedings of the 4th Canadian Conference on Computational Geometry, pp. 77\u201383, 1992."},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0095-8956(78)90059-X","volume":"24","author":"S. Fisk","year":"1978","unstructured":"S. Fisk, \u201cA short proof of Chv\u00e1tal's watchman theorem,\u201d J. Combin. Theory Ser. B, vol. 24, 1978, pp. 374.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"19_CR16","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A. Fournier","year":"1984","unstructured":"A. Fournier and D. Y. Montuno, \u201cTriangulating simple polygons and equivalent problems,\u201d ACM Transactions on Graphics, vol. 3, No. 2, 1984, pp. 153\u2013175.","journal-title":"ACM Transactions on Graphics"},{"issue":"6","key":"19_CR17","doi-asserted-by":"publisher","first-page":"2535","DOI":"10.1109\/TMAG.1983.1062810","volume":"19","author":"E. Heighway","year":"1983","unstructured":"Heighway, E., \u201cA mesh generator for automatically subdividing irregular polygons into quadrilaterals,\u201d IEEE Transactions on Magnetics, 19, 6, pp. 2535\u20132538, 1983.","journal-title":"IEEE Transactions on Magnetics"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0010-4485(88)90138-8","volume":"20","author":"K. Ho-Le","year":"1988","unstructured":"Ho-Le, K., \u201cFinite element mesh generation methods: A review and classification,\u201d Computer Aided Design, 20, pp. 27\u201338, 1988.","journal-title":"Computer Aided Design"},{"key":"19_CR19","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1007\/3-540-52846-6_106","volume":"447","author":"J. Hershberger","year":"1990","unstructured":"Hershberger, J., and S. Suri, \u201cApplications of a semi-dynamic convex hull algorithm,\u201d Proceedings of the second S.W.A.T., Lecture Notes in Computer Science 447, Bergen, Sweden, pp. 380\u2013392, 1990.","journal-title":"Proceedings of the second S.W.A.T., Lecture Notes in Computer Science"},{"issue":"1","key":"19_CR20","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1002\/nme.1620310105","volume":"31","author":"B. P. Johnston","year":"1991","unstructured":"Johnston, B. P., Sullivan, J. M. and Kwasnik, A., \u201cAutomatic conversion of triangular finite meshes to quadrilateral elements,\u201d International Journal of Numerical Methods in Engineering, vol. 31, No. 1, 1991, pp. 67\u201384.","journal-title":"International Journal of Numerical Methods in Engineering"},{"key":"19_CR21","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1137\/0604020","volume":"4","author":"J. Kahn","year":"1983","unstructured":"Kahn, J., M. Klawe, D. Kleitman, \u201cTraditional galleries require fewer watchmen,\u201d SIAM J. Algebraic Discrete Methods, 4, pp. 194\u2013206, 1983.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"A. A. Kooshesh and B. M. E. Moret, \u201cThree-coloring the vertices of a triangulated simple polygon,\u201d Pattern Recognition, vol. 25, 1992.","DOI":"10.1016\/0031-3203(92)90093-X"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"J. M. Keil and J.-R. Sack, \u201cMinimum decompositions of polygonal objects,\u201d in Computational Geometry, Ed., G. T. Toussaint, North-Holland, Amsterdam, pp. 197\u2013216.","DOI":"10.1016\/B978-0-444-87806-9.50012-8"},{"key":"19_CR24","unstructured":"Lai, M. J., \u201cScattered data interpolation and approximation by using C1 piecewise cubic polynomials,\u201d submitted for publication."},{"key":"19_CR25","doi-asserted-by":"crossref","first-page":"245","DOI":"10.3233\/FI-1978-2116","volume":"2","author":"W. Lipski Jr.","year":"1979","unstructured":"W. Lipski, Jr., E. Lodr, F. Luccio, C. Mugnal and L. Pagli, \u201cOn two dimensional data organization II, Fundanmenta Informaticae, vol. 2, 1979, pp. 245\u2013260.","journal-title":"Fundanmenta Informaticae"},{"key":"19_CR26","volume-title":"Scattered data interpolation using C2 piecewise polynomials of degree six","author":"M. J. Lai","year":"1994","unstructured":"Lai, M. J. and Schumaker, L. L., \u201cScattered data interpolation using C2 piecewise polynomials of degree six,\u201d Third Workshop on Proximity Graphs, Mississippi State University, Starkville, Mississippi, December 1\u20133, 1994."},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Lubiw, A., \u201cDecomposing polygonal regions into convex quadrilaterals,\u201d Proc. Symposium on Computational Geometry, 1985, pp. 97\u2013106.","DOI":"10.1145\/323233.323247"},{"key":"19_CR28","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A. Okabe","year":"1992","unstructured":"Okabe, A., B. Boots, and K. Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, Chichester, England, 1992."},{"key":"19_CR29","unstructured":"T. Ohtsuki, \u201cMinimum dissection of rectilinear regions,\u201d in Proc. IEEE International Symposium on Circuits and Systems, Rome, 1982, pp. 1210\u20131213."},{"key":"19_CR30","unstructured":"O'Rourke, J., Computational Geometry in C., Cambridge University Press, 1994."},{"key":"19_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"Preparata, F. P. and Shamos, M. I., Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"19_CR32","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1137\/0218056","volume":"18","author":"F. P. Preparata","year":"1989","unstructured":"Preparata, F. P. and Tamassia, R., \u201cFully dynamic point location in a monotone subdivision,\u201d SIAM Journal on Computing, vol. 18, 1989, pp. 811\u2013830.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR33","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0167-8396(90)90037-R","volume":"7","author":"E. Quak","year":"1990","unstructured":"Quak, E. and Schumaker, L. L., \u201cCubic spline fitting using data dependent triangulations.\u201d Computer-Aided Geometric Design, vol. 7, 1990, pp. 293\u2013301.","journal-title":"Computer-Aided Geometric Design"},{"key":"19_CR34","unstructured":"Ramaswami, S., Ramos, P. and G. T. Toussaint, \u201cConverting triangulations to quadrangulations,\u201d manuscript in preparation."},{"key":"19_CR35","unstructured":"Sack, J. R., \u201cAn O(n log n) algorithm for decomposing simple rectilinear polygons into convex quadrilaterals,\u201d Proc. 20th Annual Conf. on Communications, Control and Computing, Allerton, 1982, pp. 64\u201374."},{"issue":"9","key":"19_CR36","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1109\/5.163413","volume":"80","author":"V. Srinivasan","year":"1992","unstructured":"Srinivasan, V., Nackman, L. R., Tang, J.-M. and Meshkat, S. N., \u201cAutomatic mesh generation using the symmetric axis transformation of polygonal domains,\u201d Proceedings of the IEEE, vol. 80, No. 9, September 1992, pp. 1485\u20131501.","journal-title":"Proceedings of the IEEE"},{"issue":"4","key":"19_CR37","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/0010-4485(89)90050-X","volume":"21","author":"N. Sapidis","year":"1989","unstructured":"Sapidis, N. and Perucchio, R., \u201cAdvanced techniques for automatic finite element meshing from solid models,\u201d Computer Aided Design, vol. 21, No. 4, May 1989, pp. 248\u2013253.","journal-title":"Computer Aided Design"},{"key":"19_CR38","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0010-4485(79)90097-6","volume":"11","author":"N. Sugiyama","year":"1979","unstructured":"N. Sugiyama and K. Saitoh, \u201cElectron-beam exposure system AMDES,\u201d Computer Aided Design, vol. 11, 1979, pp. 59\u201365.","journal-title":"Computer Aided Design"},{"key":"19_CR39","doi-asserted-by":"crossref","first-page":"2503","DOI":"10.1002\/nme.1620261109","volume":"24","author":"W. Schroeder","year":"1988","unstructured":"Schroeder, W., and M. Shephard, \u201cGeometry-based fully automatic mesh generation and the Delaunay triangulation,\u201d International Journal for Numerical Methods in Engineering, 24, pp. 2503\u20132515, 1988.","journal-title":"International Journal for Numerical Methods in Engineering"},{"key":"19_CR40","unstructured":"Sack, J.-R. and Toussaint, G. T., \u201cA linear-time algorithm for decomposing rectilinear star-shaped polygons into convex quadrilaterals,\u201d Proc. 19th Annual Conf. on Communications, Control and Computing, Allerton, 1981, pp. 21\u201330."},{"key":"19_CR41","doi-asserted-by":"crossref","unstructured":"Sack, J.-R. and Toussaint, G. T., \u201cGuard placement in rectilinear polygons,\u201d in Computational Morphology, Ed., G. T. Toussaint, North-Holland, 1988, pp. 153\u2013175.","DOI":"10.1016\/B978-0-444-70467-2.50016-3"},{"key":"19_CR42","unstructured":"Toussaint, G. T., \u201cSolving geometric problems with the rotating calipers,\u201d Proc. IEEE MELECON 83, Athens, Greece, 1983, pp. A10002\/1\u20134."},{"key":"19_CR43","doi-asserted-by":"crossref","unstructured":"Toussaint, G. T., \u201cNew results in computational geometry relevant to pattern recognition in practice,\u201d in Pattern Recognition in Practice II, E. S. Gelsema and L. N. Kanal, Eds., North-Holland, 1986, pp. 135\u2013146.","DOI":"10.1016\/B978-0-444-87877-9.50015-7"},{"key":"19_CR44","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0167-8396(92)90031-J","volume":"9","author":"T. Wang","year":"1992","unstructured":"Wang, T., \u201cA C 2-quintic spline interpolation scheme on triangulation,\u201d Computer Aided Geometric Design, vol. 9, 1992, pp. 379\u2013386.","journal-title":"Computer Aided Geometric Design"},{"key":"19_CR45","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0031-3203(86)90010-5","volume":"19","author":"Y. Wang","year":"1986","unstructured":"Wang, Y., and J. Aggarwal, \u201cSurface reconstruction and representation of 3-d scenes,\u201d Pattern Recognition, 19, pp. 197\u2013207, 1986.","journal-title":"Pattern Recognition"},{"key":"19_CR46","volume-title":"Tech. Report 80-106","author":"S. K. Wismath","year":"1980","unstructured":"Wismath, S. K., \u201cTriangulations: An algorithmic study,\u201d Tech. Report 80-106, Queens University, Kingston, Canada, July 1980."},{"key":"19_CR47","volume-title":"Display and Analysis of Spatial Data","author":"P. Yoeli","year":"1975","unstructured":"Yoeli, P., \u201cCompilation of data for computer-assisted relief cartography,\u201d in Display and Analysis of Spatial Data, J. Davis, and M. McCullagh, eds., John Wiley & Sons, New York, 1975."},{"key":"19_CR48","volume-title":"The Finite Element Method, vol. I","author":"O. C. Zienkiewicz","year":"1989","unstructured":"Zienkiewicz, O. C. and Taylor, R. L., The Finite Element Method, vol. I, McGraw-Hill, London, 1989."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T09:31:42Z","timestamp":1640943102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}