Optimal Terminal Interconnection through Repartitioning of Randomly Divided Planes

In situations in which randomly divided planes are interconnected, the interconnection is usually reconstructed when the divided planes change owing to the newly inserted terminals based on all objects that exist in the planes.This ensures a minimum connection length, but requires a significant amount of time for reconstruction.This paper describes the minimum spanning tree (MST) that efficiently expands interconnections in a short time by repartitioning the plane when a terminal set T is interconnected in a two-dimensional plane that is randomly divided into m and new terminals are inserted.We propose a method for obtaining an optimal tree known as the Tinkered Tree that is close to the MST.With technological advancements, the construction of interconnections has become necessary anytime, anywhere.In particular, when establishing ad-hoc networks, expansion of interconnections occurs frequently.Therefore, it is anticipated that the heuristic proposed in this study will provide various benefits by enabling the rapid establishment of interconnections at a low cost in such situations.