A Network Layout Algorithm Based on the Principle of Regular Hexagons Covering a Plane

摘要

Given some discrete points on a plane, an optimal network layout was computed to make the distance between any two adjoining points less than or equal to the given value d, and to maximize the number of the given points near the network-nodes. The computing method was based on the principle of regular hexagons covering a plane. All the given coordinates were mapped to an enlarged unit, and the sufficient and necessary condition of the points P_(i1), P_(i2), ... , P_(ik) being used is that their image points in the enlarged unit can be covered by a round. By translating the center of the round in the enlarged unit, the algorithm found out the most points of being used, and sought out the optimal network layout. For any instance I and ε > 0, its feasible solution A(ε)[I] satisfies: when ε → 0, A(ε)[I] → OPT[I].