Name
Abstract | ||
|---|---|---|
Let γ C and γ D be two convex distance functions 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 γ C and distance from q by γ D . 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 and D . The bisector can contain bounded or unbounded two-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 n 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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0166-218X(00)00238-9 | Discrete Applied Mathematics - Special issue 14th European workshop on computational geometry CG'98 Selected papers |
Keywords | Field | DocType |
gauge,location problem,norm,convex distance function,bisector,different distance function,voronoi diagram,distance function,connected component,unit ball,2 dimensional | Discrete mathematics,Polygon,Combinatorics,Vertex (geometry),Ball (bearing),Regular polygon,Angle bisector theorem,Voronoi diagram,Connected component,Mathematics,Bounded function | Conference |
Volume | Issue | ISSN |
109 | 1-2 | Discrete Applied Mathematics |
ISBN | Citations | PageRank |
1-58113-068-6 | 13 | 0.95 |
References | Authors | |
7 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Icking | 1 | 364 | 33.17 |
| Rolf Klein | 2 | 237 | 19.69 |
| Lihong Ma | 3 | 76 | 8.61 |
| Stefan Nickel | 4 | 427 | 41.70 |
| Ansgar Weißler | 5 | 13 | 0.95 |