Attestation committee
Accreditation committee
Expert committee
Dispositions, instructions
Normative acts
Nomenclature
Institutions
Scientific councils
Seminars
Theses
Scientific advisers
Scientists
Doctoral students
Postdoctoral students
CNAA logo

 română | русский | english


Partitioning of polyhedra in finite dimensional normed spaces into d-convex parts with applications


Author: Băţ Ion
Degree:doctor of physics and mathematics
Speciality: 01.01.09 - Mathematical cybernetics and operation research
Year:2011
Institution: Moldova State University
Scientific council: DH 30-01.01.09-27.03.08
Moldova State University

Status

The thesis was presented on the 2 September, 2011
Approved by NCAA on the 11 November, 2011

Abstract

Adobe PDF document0.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-pattern

Summary

“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