Informatics and Applications
2018, Volume 12, Issue 2, pp 69-74
MATHEMATICAL MODEL OF OPTIMAL TRIANGULATION
- A. Batenkov
- Yu. Maniakov
- A. Gasilov
- O. Yakovlev
Abstract
The problem of synthesis of optimal planar convex triangulation is formalized. This problem arises in different applications of informatics problems and is very actual for its sections such as computer graphics and geographical information systems. The mathematical model is represented as an extremum problem with infinite number of constraints, as a minimax problem with bound variables, and as an extremum problem with additional constraints on line segments intersections of triangulation with limited number of constraints. By putting idempotent limitations on Boolean variables, the initial integer-valued problem could be solved as a general mathematical programming problem on a continuum set of answers. In addition, the comparison of results obtained by the greedy algorithm based on the represented model and Delaunay triangulation is provided.
[+] References (13)
- Gasilov, A.V., and O.A. Yakovlev. 2016. Sozdanie realistichnykh naborov dannykh dlya algoritmov trekhmernoy rekonstruktsii s pomoshch'yu virtual'noy s"emki komp'yuternoy modeli [Genereating realistic structure- from-motion datasets with a virtual shooting]. Sistemy i Sredstva Informatiki -Systems and Means of Informatics 26(2):98-107.
- Kostyuk, Yu. L., and A. L. Fuks. 1998. Priblizhennoe vychislenie optimal'noy triangulyatsii [Approximate calculation of optimal triangulation]. Geoinformatika: teoriya i praktika [Geoinformatics: Theory and practice] 1:61
66.
- Lisin, A. V., and R. T. Faizullin. 2013. Evristicheskiy algoritm poiska priblizhennogo resheniya zadachi Shteynera, osnovannyy na fizicheskikh analogiyakh [Heuristic algo-rithm for finding approximate solution of Steiner problem based on physical analogies]. Computer Optics 37(4):503- 510.
- Preparata, F., andM. Shamos. 1985. Computational geom-etry: An introduction. - New York - Berlin - Heidelberg - Tokyo: Springer-Verlag. 398 p.
- Skvortsov, A. V., and N. S. Mirza. 2006. Algoritmy postroeniya i analiza triangulyatsii [Generation and analysis algorithms of triangulation]. Tomsk: Tomsk State University. 168 p.
- Skvortsov, A. V. 2002. Triangulyatsiya Delone i eeprimene- nie [Delaunay triangulation and its application]. Tomsk: Tomsk State University. 128 p.
- Ivanovskiy, S. A., and S.K. Simonchik. 2007. Algoritmy vychislitel'noy geometrii. Peresechenie otrezkov: metod zametaniya ploskosti [Computational geometry algory- thms: Plane covering method]. Komp'yuternye instrumenty v obrazovanii [Computer instruments in education] 4:1833.
8
- Igoshin, V. I. 2008. Matematicheskaya logika i teoriya algoritmov [Mathematical logic and algorithms' theory]. Moscow: Akademiya. 448 p.
- Volkov, I. K., and A. N. Kanatnikov 2002. Integral'nye preobrazovaniya i operatsionnoe ischislenie [Integral trans-formation and operational calculus]. 2nd ed. Moscow: MSTU. 228 p.
- Bronshtein, I. N., and K. A. Semendyaev. 1964. Spravoch- nik po matematike [Mathematics handbook]. Moscow: Nauka. 608 p.
- Potekhina, E. A. 2012. Primenenie proizvedeniya Adamara v zadache perechisleniya uporyadochennykh razbieniy [Application of Adamar's multiplication for enumeration of ordered decompositions problem]. Naukoemkie tekhnologii [Science Technologies] 13(8):58-65.
- Gantmakher, F. R. 1966. Teoriya matrits [The matrix the-ory]. 2nd ed. Moscow: Nauka. 576 p.
- Himmelblau, D. M. 1972. Applied nonlinear programming. New York, NY: McGraw-Hill Book Co. 498 p.
[+] About this article
Title
MATHEMATICAL MODEL OF OPTIMAL TRIANGULATION
Journal
Informatics and Applications
2018, Volume 12, Issue 2, pp 69-74
Cover Date
2018-05-30
DOI
10.14357/19922264180210
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
mathematical model; triangulation; Delaunay triangulation
Authors
A. Batenkov  , Yu. Maniakov , A. Gasilov , and O. Yakovlev
Author Affiliations
Orel Branch of the Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 137 Moskovskoe Shosse, Orel 302025, Russian Federation
|