2-site Voronoi triangle centers

The idea of a 2-site Voronoi diagram was pioneered by Barequet, Dickerson, and Drysdale in a WADS 1999 paper later published in Discrete Applied Math. 2002. The basic idea is that you have a function \( d(p,q;x) \) that tells you the distance from an unordered pair of sites \( \{p,q\} \) to another point \( x \) in the plane; given a collection of sites, you want to divide the plane up into regions so that the region containing a point \( x \) tells you which pair of sites is closest to \( x \) (or in some cases farthest from \( x \)). Since their work there have been several followup papers including one in which I was involved.

If three sites are given, then these sites determine three pairs of sites, three regions in the Voronoi diagram, and (usually) one or more Voronoi vertices where all three sites meet. Often, these vertices define triangle centers: special points defined from the triangle of the three sites, such that applying a similarity transformation to the plane commutes with constructing the given point. Technically, to get a triangle center out of a 2-site Voronoi diagram, the distance function has to be invariant under congruences of the plane, and if a triangle \( pqx \) is scaled by a factor of \( s \) then the distance \( d(p,q;x) \) has to scale by a factor of \( s^e \) for some constant scaling exponent \( e \) (possibly zero). But this scaling requirement is true of many natural functions that you might want to use as distances.

By now, thousands of different triangle centers have been studied. Which of them can be generated from 2-site Voronoi diagrams in this way? Here are some examples. (The X(...) numbers are references to Clark Kimberling's Encyclopedia of Triangle Centers.)

• If \( d(p,q;x) \) is defined as the Euclidean distance from point \( x \) to line \( pq \), with scaling exponent \( 1, \) then the level sets of this distance function are infinite slabs having \( pq \) as their centerline. For a given triangle \( pqr, \) the 2-site Voronoi diagram for this distance function has seven junctions. At the three points where two lines cross, four cells of the diagram meet, two for each of the two lines. And at four other points (one inside the triangle and three outside), all three cells of the diagram meet. The one inside the triangle is the incenter X(1), a triangle center that is the center point of a circle inscribed inside the triangle. The other three of these Voronoi vertices are the excenters, center points of circles that touch the three lines but are exterior to the triangle, and are not individually triangle centers.

  In the figure below, the level sets of the distances from the three lines are indicated by the red, blue, and yellow shading. The Voronoi diagram boundaries are the green line segments, and the incenter is the green Voronoi vertex inside the triangle. The excenters are outside the margins of the drawing.

  

  Alternatively, we could have defined \( d(p,q;x) \) to be the Euclidean distance from point \( x \) to line segment \( pq, \) giving more complicated stadium-shaped level sets and only one Voronoi vertex at the incenter.

• If \( d(p,q;x) \) is the area of triangle \( pqx, \) then the scaling exponent is \( 2 \) and the level sets of the distance function are again slabs, with longer line segments having narrower slabs for the same distance. There is a Voronoi vertex at the centroid of the triangle X(2), because at that point all three of the triangles \( pqx, \) \( prx, \) and \( qrx \) have the same area as each other.

• If \( d(p,q;x) \) is the sum of distances \( px+qx, \) then the scaling exponent is \( 1, \) and the level sets of the distance function are ellipses. There is a Voronoi vertex at the circumcenter X(3); it is inside the triangle if it is acute, outside if it is obtuse, and at the midpoint of the hypotenuse if it is right.

• If \( d(p,q;x) \) is the Euclidean distance from \( x \) to the midpoint of \( pq, \) then the level sets of the distance function are just circles centered on this midpoint, and the scaling exponent is \( 1. \) The Voronoi vertex is at the nine-point center of the triangle, X(5).

• If \( d(p,q;x) \) is the ratio of two quantities, the distance of \( x \) from line \( pq \) and the length of segment \( pq, \) then the scaling exponent is \( 0. \) The level sets of the distance function are slabs, as for the incenter and centroid, but scaled differently, and there is a Voronoi vertex at the symmedian X(6).

• If \( d(p,q;x) \) is the angle subtended by segment \( pq, \) as viewed from \( x, \) then the level sets of the distance function are lunes centered on the sides of the triangle, the scaling exponent is \( 0, \) and there is a Voronoi vertex at the Fermat point of the triangle, which for not-too-obtuse triangles coincides with X(13).

• If \( d(p,q;x) \) is the perimeter of triangle \( pqx, \) then the scaling exponent is \( 1 \) and the level sets of the distance function are ellipses. In this case there is a Voronoi vertex at the isoperimetric point X(175).

• If \( d(p,q;x) \) is the ratio of the sum of distances \( px+qx \) to the length of segment \( pq \) (that is, the dilation of the path \( pxq \)) then the scaling exponent is \( 0 \) and the level sets are ellipses again. The associated triangle center is the dilation center X(3513).

• If \( d(p,q;x) \) is the inradius of triangle \( pqx, \) then the scaling exponent is \( 1. \) I think the level sets of the distance function are hyperbolae but I haven't proved this. There is a Voronoi vertex at the mysterious congruent incircles point of the triangle, X(5394).

Points X(31), X(32), X(75), and X(76) are also Voronoi vertices of differently-scaled distances from line \( pq. \) One can generate even more examples (although not necessarily interesting ones) by multiplying together two or more of these distance functions, or adding together functions with the same scaling exponent.

Despite all these examples, it's not clear to me how to tell whether a triangle center is or isn't a 2-site Voronoi vertex, or whether there exists a center that is not a 2-site Voronoi vertex. The most obvious center for which I haven't found a good 2-site distance function is the orthocenter X(4), the point where the perpendiculars to each side through the opposite vertex meet. Is it a 2-site Voronoi vertex for some distance function, and if so, what is the function?

Comments: