
StatusThe thesis was presented on the 2 September, 2011Approved by NCAA on the 11 November, 2011 Abstract– 0.34 Mb / in romanian 
“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: dconvex set, point of local nondconvexity, geometric multidimensional
polyhedron, face, gpolytope, gpolyhedral complex, dividing, bipartite graph, independent
set, dXpattern.
The study in this paper concerns a current area of research related to dconvexity
theory, namely, the problem of partitioning of geometric polyhedra in finite dimensional
normed spaces into dconvex pieces.
The purpose is to establish some new results that relate to the partition of polyhedra in
finite dimensional normed spaces into dconvex parts. The research objectives provide the
generalization of polyhedral complexes by introducing the gpolyhedral complexes and their
examination, the statement of the minimum number of dconvex 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 dconvex 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 dconvex 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 2dimensional and 3dimensional 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