One approach for computing simple polygons on a given point set in the plain
Електронний науковий архів Науково-технічної бібліотеки Національного університету "Львівська політехніка"
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
One approach for computing simple polygons on a given point set in the plain
|
|
| Creator |
Fisunenko, Andriy
|
|
| Contributor |
Taras Shevchenko National University of Kyiv
|
|
| Subject |
simple polygon
simple polygonal chain polygonization mutual visibility graph biconnected component bridge |
|
| Description |
We consider the problem of computing all possible simple polygons embrasing every point of a given finite point set in the plane. The developed approach is based on topological analysis of mutual visibility graphs of all free points and end points of a constructed chain. We found several new necessary conditions for existence of simple polygonal chains which are based on checking collocations of articulation points, bridges and biconnected components of such graphs. These conditions can be effectively applied for reducing trees of exhaustive search for all possible polygons on the given point set or for their random generation. |
|
| Date |
2018-03-01T14:25:51Z
2018-03-01T14:25:51Z 2015 |
|
| Type |
Conference Abstract
|
|
| Identifier |
Fisunenko A. One approach for computing simple polygons on a given point set in the plain / Andriy Fisunenko // Litteris et Artibus : proceedings of the 5th International youth science forum, November 26–28, 2015, Lviv, Ukraine / Lviv Polytechnic National University. – Lviv : Lviv Polytechnic Publishing House, 2015. – P. 44–45. – Bibliography: 7 titles.
http://ena.lp.edu.ua:8080/handle/ntb/39492 |
|
| Language |
en
|
|
| Relation |
[1] E. D. Demaine, J. S. B. Mitchell, J. O'Rourke, "The Open Problems Projects," http://cs.smith.edu/. [Online]. Available: http://cs.smith.edu/~orourke/TOPP/. [Accessed: Oct. 25, 2015]. [2] ComPoSe, Eurocores-EuroGIGA, "Combinatorics of Point Sets and Arrangements of Objects," http://www.eurogiga-compose.eu. [Online]. Available: - http://www.eurogiga-compose.eu/about.php. [Accessed: Oct. 25, 2015]. [3] Rectilinear Crossing Number, "Rectilinear Crossing Number Project," http://dist.ist.tugraz.at [Online]. Available: http://dist.ist.tugraz.at/cape5/. [Accessed: Oct. 25, 2015]. [4] V. Muravitskiy, V. Tereshchenko, "Generating a simple polygonalizations," In Proceedings of 15th International Conference on Information Visualisation, pp.502-506, Jul. 2011. [5] Andriy Fisunenko, "Generation of simple polygons by cutting out and building up convex hulls". Bulletin of Taras Shevchenko National University of Kyiv, Series Physics & Mathematics, vol. Spetsvypusk, pp.190-193., Dec. 2013. [6] T. Auer, M. Held, "Heuristics for the generation of random polygons," In Proceedings of the 8th Canadian Conference on Computational Geometry, Ottawa, Ontario, pp.38-43, Jan. 2006. [7] J. A. Shuffelt, H. J. Berliner, "Generating Hamiltonian circuits without backtracking from errors," Theoretical Computer Science Journal, vol. 132 (s 1-2), pp.347-375, Sep. 1994.
|
|
| Format |
44-45
application/pdf |
|
| Coverage |
UA
Lviv |
|
| Publisher |
Lviv Polytechnic Publishing House
|
|