On Hamiltonian Triangulations in Simple Polygons (Extended Abstract)
作者： Giri Narasimhan
关键词: Simple polygon 、 Rendering (computer graphics) 、 Point set triangulation 、 Combinatorics 、 Dual graph 、 Visibility graph 、 Pitteway triangulation 、 Hamiltonian path 、 Hamiltonian (quantum mechanics) 、 Mathematics
摘要: An n-vertex simple polygon P is said to have a Hamiltonian Triangulation if it has triangulation whose dual graph contains path. Such triangulations are useful in fast rendering engines Computer Graphics. We give new characterization of polygons with triangulations. and use devise O(n log n)-time algorithms recognize such polygons.
springer.com
sci-hub.st 参考文章(9)
Gautam Das, Paul J. Heffernan, Giri Narasimhan, Finding all weakly-visible chords of a polygon in linear time scandinavian workshop on algorithm theory. ,vol. 1, pp. 433- 457 ,(1994) , 10.1007/3-540-58218-5_11
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
Gautam Das, Paul J. Heffernan, Giri Narasimhan, LR-visibility in polygons Computational Geometry: Theory and Applications. ,vol. 7, pp. 37- 57 ,(1997) , 10.1016/0925-7721(95)00042-9
Esther M. Arkin, Martin Held, Joseph S. B. Mitchell, Steven S. Skiena, Hamiltonian triangulations for fast rendering The Visual Computer. ,vol. 12, pp. 429- 444 ,(1996) , 10.1007/BF01782475
Paul J. Heffernan, An optimal algorithm for the two-guard problem Proceedings of the ninth annual symposium on Computational geometry - SCG '93. pp. 348- 358 ,(1993) , 10.1145/160985.161163
Joseph O'Rourke, Art gallery theorems and algorithms ,(1987)
L. H. Tseng, P. Heffernan, D. T. Lee, Two Guard Walkability of Simple Polygons International Journal of Computational Geometry and Applications. ,vol. 08, pp. 85- 116 ,(1998) , 10.1142/S0218195998000060
Christian Icking, Rolf Klein, The two guards problem symposium on computational geometry. pp. 166- 175 ,(1991) , 10.1145/109648.109667
Steven Skiena, Amitabh Varshney, Francine Evans, Optimizing triangle strips for fast rendering ieee visualization. pp. 319- 326 ,(1996) , 10.5555/244979.245626