Partitioning of polyhedra in finite dimensional normed spaces into d-convex parts with applications
|
StatusThe thesis was presented on the 2 September, 2011Approved by NCAA on the 11 November, 2011 Abstract – 0.34 Mb / in romanian |
Keywords
d-convex set, point of local non-d-convexity, geometric multidimensional polyhedron, face, g-polytope, g-polyhedral complex, dividing, bipartite graph, independent set, d-X-patternSummary
“Partitioning of polyhedra in finite dimensional normed spaces into d-
convex parts with applications” submitted by Ion B˘at¸ to the Moldova State University in
partial fulfillment of the requirements for the degree of Doctor in Physics and Mathematics,
speciality 01.01.09 – Mathematical Cybernetics and Operations Research.
The thesis has been elaborated in Chisinau, Moldova State University, in 2011. It is
written in Romanian and contains introduction, three chapters, general conclusions and
recommendations, a bibliography of 109 titles, two appendices, 105 pages of main text and
22 figures. The results are published in 7 scientific papers.
Keywords: d-convex set, point of local non-d-convexity, geometric multidimensional
polyhedron, face, g-polytope, g-polyhedral complex, dividing, bipartite graph, independent
set, d-X-pattern.
The study in this paper concerns a current area of research related to d-convexity
theory, namely, the problem of partitioning of geometric polyhedra in finite dimensional
normed spaces into d-convex pieces.
The purpose is to establish some new results that relate to the partition of polyhedra in
finite dimensional normed spaces into d-convex parts. The research objectives provide the
generalization of polyhedral complexes by introducing the g-polyhedral complexes and their
examination, the statement of the minimum number of d-convex pieces into which a geomet-
ric multidimensional polyhedron can be partitioned, the development and implementation
of certain heuristic polynomial algorithms for the maximum independent set problem.
Novelty and scientific originality. In the concepts of PL manifold with boundary
and handle of index p, it has been defined the notion of geometric polyhedron of genus q in a
finite dimensional Euclidean space. It has been obtained a number of properties of the faces
of geometric multidimensional polyhedra. Formulas were derived for the minimum number
of d-convex pieces into which a geometric multidimensional polyhedron both without holes
and with holes can be partitioned. It is original the application of new procedures for the
development of heuristic polynomial algorithms for the maximum independent set problem.
Theoretical significance and applied value of the thesis. Theoretically, the obtain-
ing of formulas for the minimum number of d-convex parts into which is being partitioned a
geometric multidimensional polyhedron without holes and with holes, successfully ends the
research carried out for decades in this direction of mathematicians and computer scientists
from our country and aboard. Making software tools for the maximum independent set
problem as well as designing of approximation polynomial algorithms for the problem of ge-
ometric polyhedra partition into 2-dimensional and 3-dimensional normed spaces, represents
the applied value of this paper.
Implementation of scientific results. The results obtained in the thesis can be
used to resolve problems with applicative character in various fields such as computational
geometry, computer graphics, VLSI engineering, artificial intelligence, data compression,
image processing, pattern recognition, coding theory, fault diagnosis and others.
7
Oficial Reviewers
- Dumitru Lozovanu
doctor habilitat, professor, Moldova State University - Anatol Prisăcaru
doctor, associate professor (docent)
Council's Members
- Mitrofan Cioban, president
doctor habilitat, professor - Sergiu Cataranciuc, secretary
doctor habilitat, professor, Moldova State University - Dumitru Solomon, member
doctor habilitat, associate professor (docent), Moldova State University - Dumitru Zambiţchi, member
doctor, associate professor (docent) - Oleg Topală, member
doctor, associate professor (docent)
Theses
