Approximate optimization of drawing sequence on restricted connection between segments or points

The problem of finding the most efficient drawing path round many line segments (or points) scattered in a plane or space arises in various fields of engineering. As it is NP-hard, several approximate methods for solving it have been developed. In a previous paper, one of the authors has also proposed a kind of divide-and-conquer method, called stepwise clustering method. In this paper, the stepwise clustering method is extended to the efficient drawing path problem under some restrictions in connecting segments, e.g., a restriction that two segments cannot be connected if their attributes meet some previously assigned conditions. The method’s advantages are illustrated by three numerical examples: it is quite fast, and it finds good paths. [In Japanese.]