Date of Award

10-1-2021

Publication Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Edge-disjoint, Hamiltonian path, Non-crossing, Packing, Spanning path, Spanning tree

Supervisor

A. Biniaz

Supervisor

A. Mukhopadhyay

Rights

info:eu-repo/semantics/openAccess

Abstract

The term packing refers to the arrangement of multiple geometrical structures or shapes such as circles, squares, triangles, or polygons into a fixed and finite set of points. The geometric structures to be packed can also be trees and paths. Packing is also possible in a 3-dimensional space with geometric structures such as spheres, cylinders, and cubes.

The concept of packing was introduced more than half a century ago. Since then, many researchers have studied the packing strategies of different geometric structures in different configurations of point-set. Packing strategies help to construct and arrange multiple geometric structures in a predetermined bounded space; hence, it can be classified as an optimization problem, as we are trying to allocate the optimal space for resources in a finite bounded space. The better the efficiency of the algorithm, the greater number of items that can be packed. Packing geometrical structures have applications in the storage, transportation, and transmission of objects in fields like automobile, aerospace, and naval industries.

Since, in real-life scenarios, resources are finite, and space is limited; thus it raises the question, how to efficiently use limited space for accommodating multiple resources. However, packing multiple geometric structures can raise some design considerations. In our research, we have studied the packing of non-self-crossing, edge-disjoint plane spanning paths and have obtained some promising results. We further address some design considerations and provide a different approach on packing at least two non-self-crossing, edge-disjoint plane spanning paths into a point-set.

Download

Share

COinS