Properties and an Approximation Algorithm of Round-Tour Voronoi Diagrams

This paper proposes a new generalization of the Voronoi diagram. Consider two kinds of facilities located in a city, for example, restaurants and bookstores. We want to visit both and return to our house. To each pair of a restaurant and a bookstore is assigned a region such that a resident in this region can visit them in a shorter round tour than visiting any other pair. The city is partitioned into these regions according to which pair of a restaurant and bookstore permits the shortest round tour. We call this partitioning a "round-tour Voronoi Diagram" for the restaurants and bookstores. We study the basic properties of this Voronoi diagram and consider an efficient algorithm for its approximate construction.