Distance k-Sectors Exist

Keiko Imai, Akitoshi Kawamura, Jiří Matoušek, Daniel Reem and Takeshi Tokuyama. Distance k-sectors exist. Computational Geometry: Theory and Applications 43(9), 713–720, November 2010. DOI = 10.1016/j.comgeo.2010.05.001

Keiko Imai, Akitoshi Kawamura, Jiří Matoušek, Daniel Reem and Takeshi Tokuyama. Distance k-sectors exist. In the Proceedings of the 26th Annual ACM Symposium on Computational Geometry (SoCG), pages 210–215, Snowbird, Utah, USA, June 2010. DOI = 10.1145/1810959.1810996

Keiko Imai, Akitoshi Kawamura, Takeshi Tokuyama, Jiří Matoušek and Daniel Reem. Distance k-sectors exist. IEICE Technical Committee on Theoretical Foundations of Computing, Fukuoka, Japan, January 25, 2010. IEICE Technical Report, vol. 109, no. 391, COMP2009-41, pp. 17–22. In Japanese.

Abstract

The bisector of two nonempty sets P and Q in a metric space is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k is an integer, is a (k-1)-tuple (C_1, C_2, ..., C_{k-1}) such that C_i is the bisector of C_{i-1} and C_{i+1} for every i = 1, 2, ..., k-1, where C_0 = P and C_k = Q. This notion, for the case where P and Q are points in Euclidean plane, was introduced by Asano, Matousek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance trisector in this special case. We prove the existence of a distance k-sector for all k and for every two disjoint, nonempty, closed sets P and Q in Euclidean spaces of any (finite) dimension, or more generally, in proper geodesic spaces (uniqueness remains open). The core of the proof is a new notion of k-gradation for P and Q, whose existence (even in an arbitrary metric space) is proved using the Knaster-Tarski fixed point theorem, by a method introduced by Reem and Reich for a slightly different purpose.

Key words
distance k-sectors, Knaster–Tarski fixed point theorem