TY - GEN
T1 - Distance k-sectors exist
AU - Imai, Keiko
AU - Kawamura, Akitoshi
AU - Matoušek, Jiří
AU - Reem, Daniel
AU - Tokuyama, Takeshi
N1 - Funding Information:
A.K. is supported by the Nakajima Foundation and the Natural Sciences and Engineering Research Council of Canada. The part of this research by T.T. was partially supported by the JSPS Grant-in-Aid for Scientific Research (B) 18300001.
PY - 2010
Y1 - 2010
N2 - The bisector of two nonempty sets P and Q in ℝd is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k ≥ 2 is an integer, is a (k -1)-tuple (C1,C2, . . . ,Ck-1) such that Ci is the bisector of C i-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 ℝ2, was introduced by Asano, Matoušek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance 3-sector 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 (uniqueness remains open), or more generally, in proper geodesic spaces. 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.
AB - The bisector of two nonempty sets P and Q in ℝd is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k ≥ 2 is an integer, is a (k -1)-tuple (C1,C2, . . . ,Ck-1) such that Ci is the bisector of C i-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 ℝ2, was introduced by Asano, Matoušek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance 3-sector 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 (uniqueness remains open), or more generally, in proper geodesic spaces. 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.
UR - http://www.scopus.com/inward/record.url?scp=77954660343&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954660343&partnerID=8YFLogxK
U2 - 10.1145/1810959.1810996
DO - 10.1145/1810959.1810996
M3 - Conference contribution
AN - SCOPUS:77954660343
SN - 9781450300162
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 210
EP - 215
BT - Proceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
T2 - 26th Annual Symposium on Computational Geometry, SoCG 2010
Y2 - 13 June 2010 through 16 June 2010
ER -