2009/12/21 by Keiko Imai, Akitoshi Kawamura, Jiřı́ Matoušek +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #cs.CG #math.MG
paper · pdf · doi:10.1016/j.comgeo.2010.05.001
published as Computational Geometry 43(9):713-720, November 2010 · 10 pages, 5 figures
arxiv created 2009/12/21 · openalex publication_date 2010/05/28 · crossref created 2010/05/28 · arxiv updated 2010/07/19 · crossref issued 2010/11/01 · crossref published 2010/11/01 · crossref published-print 2010/11/01 · crossref deposited 2019/05/29 · openalex created_date 2025/10/10 · crossref indexed 2026/06/06 · openalex updated_date 2026/08/01
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 (C1, C2, ..., Ck-1) such that Ci is the bisector of Ci-1 and Ci+1 for every i = 1, 2, ..., k-1, where C0 = P and Ck = 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.