摘要: Given a set S such as polygon or of points, quadrangulation is partition the interior S, if polygon, convex hull into quadrangles (quadrilaterals) obtained by inserting edges between pairs points (diagonals vertices polygon) that intersect each other only at their end points. Not all polygons sets admit quadrangulations, even when are not required to be (convex quadrangulations). In this paper we briefly survey some recent results concerning characterization those planar always quadrangulations and non-convex) well related computational problems.
springer.com
sci-hub.st 参考文章(40)
Jörg-Rüdiger Sack, Godfried T. Toussaint, Guard Placement in Rectilinear Polygons Machine Intelligence and Pattern Recognition. ,vol. 6, pp. 153- 175 ,(1988) , 10.1016/B978-0-444-70467-2.50016-3
Godfried T. Toussaint, Solving geometric problems with the rotating calipers Proceedings of the IEEE MELECON, 1983. ,(1983)
J. Mark KEIL, Jorg-R. SACK, Minimum Decompositions of Polygonal Objects Machine Intelligence and Pattern Recognition. ,vol. 2, pp. 197- 216 ,(1985) , 10.1016/B978-0-444-87806-9.50012-8
John Hershberger, Subhash Suri, Applications of a semi-dynamic convex hull algorithm scandinavian workshop on algorithm theory. pp. 380- 392 ,(1990) , 10.1007/3-540-52846-6_106
Godfried T. Toussaint, NEW RESULTS IN COMPUTATIONAL GEOMETRY RELEVANT TO PATTERN RECOGNITION IN PRACTICE Pattern Recognition in Practice. pp. 135- 146 ,(1986) , 10.1016/B978-0-444-87877-9.50015-7
Esther M. Arkin, Martin Held, Joseph S. B. Mitchell, Steven S. Skiena, Hamiltonian triangulations for fast rendering Algorithms — ESA '94. pp. 36- 47 ,(1994) , 10.1007/BFB0049395
Prosenjit Bose, Godfried Toussaint, No Quadrangulation is Extremely Odd international symposium on algorithms and computation. pp. 372- 381 ,(1995) , 10.1007/BFB0015443
MARSHALL BERN, DAVID EPPSTEIN, MESH GENERATION AND OPTIMAL TRIANGULATION WORLD SCIENTIFIC. pp. 23- 90 ,(1992) , 10.1142/9789812831699_0003
W. J. Schroeder, M. S. Shephard, Geometry-based fully automatic mesh generation and the delaunay triangulation International Journal for Numerical Methods in Engineering. ,vol. 26, pp. 2503- 2515 ,(1988) , 10.1002/NME.1620261109
Anna Lubiw, Decomposing polygonal regions into convex quadrilaterals symposium on computational geometry. pp. 97- 106 ,(1985) , 10.1145/323233.323247