# Segments of Voronoi Diagrams on smooth manifolds. Are they geodesics?

Let $S$ be a patch of a smooth 2-manifold in $\mathbb{R}^3$, and pick two distinct points $a,\ b \in S$. Let $c$ be the set of points on $S$ equidistant to $a$ and $b$, where distance is defined by shortest paths on the surface. Call $c$ a bisector.

A bisector may be non-manifold at points (a torus with a long, thin rod attached has pairs of points with such bisectors). A bisector is, in a sense, a generalized kind of medial axis or Voronoi Diagram.

To illustrate, given a few points on $S$ we may construct a so called geodesic Voronoi Diagram. It's easy to see that it is made of segments of bisectors:

The resulting figure looks analogous to a classical Voronoi Diagram. How far does the analogy extend?

Q. Suppose we have a connected 1-manifold segment of the bisector of $a$ and $b$. Is it a segment of a geodesic on $S$?.

Credit:

The Illustration is from Franz Wolter's web article "Cut Locus and Medial Axis in the Euclidean Space and on Surfaces"

I also shamelessly copied from Joseph O'Rourke's related MO post.

-

It is a theorem of JK Beem (1975) Pseudo-Riemannian Manifolds with Totally Geodesic Bisectors, that bisectors are geodesics if and only if the manifold has constant curvature.

-
This paper only says that bisectors in $M$ are totally geodesic if and only if $M$ has constant curvature. This makes no difference for the original poster's question which was one-dimensional, but isn't it true that a bisector $B$ can be geodesic (the geodesic between any two distinct points in $B$ is contained in $B$) without being totally geodesic? I'm thinking, for example, of products. – John Voight Aug 1 '15 at 0:05
Nevermind: on a small enough neighborhood around each point of the bisector, the geodesics from the point cover all possible tangent directions. In particular, if the bisector contains all geodesics between points, then it is totally geodesic. – John Voight Aug 1 '15 at 15:42

The simplest example would seem to be an egg of revolution, not an ellipsoid, with one point the North Pole at the pointy end, while the other is the pole at the broad end. The bisector is a circle of revolution, a parallel, but not an equator..

Note that here, if we take a plane containing the axis of revolution and intersect with the figure, the resulting meridian is a geodesic, while also being a bisector for any pair of points symmetric across the plane.

A less symmetric example starts with the xy plane in $\mathbf R^3,$ then introducing a radially symmetric hill with support within, say, the standard unit disk. The bisector of the points $(8,0)$ and $(10,0)$ is still the geodesic $x=9.$ However, the bisector of the points $(-2,0)$ and $(2,\frac{1}{2})$ is a little peculiar near the origin.

-

More of a comment than an answer. Chapter 5 of William Goldman's book `Complex Hyperbolic geometry' has a great detail of information on the bisectors in complex hyperbolic space (so real dimension 2n, n>1) and has many pictorial representations of them. They are beautiful objects. Goldman asserts that there are no real codimension 1 totally geodesic submanifolds in complex hyperbolic space so the bisectors cannot be totally geodesic. The bisectors of complex hyperbolic space are minimal surfaces, all congruent to each other.

-
@Richard: I took the liberty of adding a figure from Goldman's 1998 preview of the book, which I found online (I don't have the book itself). – Joseph O'Rourke May 21 '12 at 20:14

See also the earlier MO question "Delaunay triangulations and convex hulls," where I posted this image:

Of course here, as per the theorem Igor quotes, the bisectors are geodesics.

-

Some theoretic reaults on bisecotr and Voronoi diagram on 2-manifold triangular surface are presented in:

Yong-Jin Liu, Zhan-Qing Chen, Kai Tang. Construction of Iso-contours, Bisectors and Voronoi Diagrams on Triangulated Surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 33, No. 8, pp. 1502-1517, 2011.

-