Title :
Distance Trisector Curves in Regular Convex Distance Me
Author :
Asano, Tetsuo ; Kirkpatrick, David
Author_Institution :
Sch. of Inf. Sci., JAIST, Nomi
Abstract :
Given two points A and B in the plane, we are interested in separating them by two curves Ca and Cb such that Ca is equidistant from A and Cb, and Cb is equidistant from B and Ca- Such curves generalize the familiar notion of a bisector curve, and form the basis of a new kind of Voronoi diagram called a Zone diagram. These curves, which are referred to as distance trisector curves, have been studied in the Euclidean metric where they exist, are unique, and admit efficient approximations. Nevertheless, they have no known expression in terms of elementary functions and are conjectured to be non-algebraic. In this paper, we study distance trisector curves with respect to a parameterized family of distance metrics that provide arbitrarily close approximations to the Euclidean distance. The advantage of studying distance trisectors in this setting is that they have a simple piecewise-linear description and an efficient (exact) construction. We show that distance trisectors defined in this way provide a conceptually simple alternative proof of the existence and uniqueness of Euclidean trisector curves.
Keywords :
approximation theory; computational geometry; curve fitting; Euclidean metric; Voronoi diagram; arbitrary close approximation; distance trisector curve; elementary function; piecewise-linear description; regular convex distance metrics; zone diagram; Computer science; Equations; Euclidean distance; Information science; Piecewise linear techniques; Polynomials; Time series analysis;
Conference_Titel :
Voronoi Diagrams in Science and Engineering, 2006. ISVD '06. 3rd International Symposium on
Conference_Location :
Banff, Alberta, BC
Print_ISBN :
0-7695-2630-6
DOI :
10.1109/ISVD.2006.21