TY - INPR
A1 - Icking, Christian
A1 - Klein, Rolf
A1 - Ma, Lihong
A1 - Nickel, Stefan
A1 - Weissler, Ansgar
T1 - On Bisectors for Different Distance Functions
N2 - Let rC and rD be two convexdistance funtions in the plane with convex unit balls C and D. Given two points, p and q, we investigate the bisector, B(p,q), of p and q, where distance from p is measured by rC and distance from q by rD. We provide the following results. B(p,q) may consist of many connected components whose precise number can be derived from the intersection of the unit balls, C nd D. The bisector can contain bounded or unbounded 2-dimensional areas. Even more surprising, pieces of the bisector may appear inside the region of all points closer to p than to q. If C and D are convex polygons over m and m vertices, respectively, the bisector B(p,q) can consist of at most min(m,n) connected components which contain at most 2(m+n) vertices altogether. The former bound is tight, the latter is tight up to an additive constant. We also present an optimal O(m+n) time algorithm for computing the bisector.
T3 - Report in Wirtschaftsmathematik (WIMA Report) - 43
KW - Bisector
KW - convex distance funtion
KW - gauge
KW - location problem
KW - norm
KW - Voronoi diagram
Y1 - 1999
UR - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/517
UR - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-4860
ER -