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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.comgeo.2010.05.001 | Computational Geometry: Theory and Applications |
Keywords | Field | DocType |
arbitrary metric space,special case,proper geodesic space,metric space,euclidean plane,distance k-sectors,equal distance,distance k-sector,new notion,euclidean space,distance trisector,vlsi design,fixed point theorem | Integer,Discrete mathematics,Uniqueness,Combinatorics,Disjoint sets,Closed set,Euclidean geometry,Metric space,Mathematics,Geodesic,Fixed-point theorem | Journal |
Volume | Issue | ISSN |
43 | 9 | Computational Geometry 43(9):713-720, November 2010 |
Citations | PageRank | References |
1 | 0.37 | 7 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Keiko Imai | 1 | 83 | 16.53 |
Akitoshi Kawamura | 2 | 102 | 15.84 |
Jiří Matoušek | 3 | 1711 | 179.65 |
Daniel Reem | 4 | 77 | 9.11 |
Takeshi Tokuyama | 5 | 1179 | 417.31 |