Name
Abstract | ||
|---|---|---|
The bisector of two nonempty sets P and Q in R(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 (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 R(2), 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 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 ( nite) 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 xed point theorem, by a method introduced by Reem and Reich for a slightly di erent purpose. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1810959.1810996 | PROCEEDINGS OF THE TWENTY-SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'10) |
Keywords | DocType | Volume |
distance k-sectors, Knaster-Tarski xed point theorem | Conference | abs/0912.4 |
Issue | Citations | PageRank |
9 | 1 | 0.37 |
References | Authors | |
4 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keiko Imai | 1 | 83 | 16.53 |
| Akitoshi Kawamura | 2 | 102 | 15.84 |
| Jirí Matousek | 3 | 763 | 76.77 |
| Daniel Reem | 4 | 77 | 9.11 |
| Takeshi Tokuyama | 5 | 1179 | 417.31 |