Where you have a triangle center defined by the intersection point of three lines or curves, you often also have a Voronoi diagram or minimization diagram whose cells have those lines as boundaries. For the circumcenter, equidistant from the three vertices of a triangle, the diagram is the classical Voronoi diagram of those three points. For the incenter, equidistant from the three sides, the diagram is the medial axis of the triangle. The Fermat point (when it doesn’t degenerate to a vertex) comes from a diagram that tells you which of the three sides of the triangle spans the widest field of view.

So when I posted recently about Cartesian triangle centers defined by an equality of areas of three bounding boxes, I had in mind a minimization diagram for bounding box area, or actually the signed area \((x-x_i)(y-y_i)\) of the bounding box of the moving point \((x,y)\) and a fixed site \((x_i,y_i)\). Here’s one of these diagrams for six points:

Minimization diagram for signed bounding box area

If you subtract \(xy\) from the signed areas, you don’t change the minimization diagram (because you’re subtracting the same thing from all the signed areas) but it makes the functions you’re minimizing become linear in \(x\) and \(y\), explaining the polygonal shape and linear boundaries of the cells in the minimization diagram. As the previous post already described, the bisector between any two cells is the diagonal line of the bounding box of two sites.

I use these diagrams in a paper to appear in the Canadian Conference on Computational Geometry, now online as a preprint: “Dynamic products of ranks” (arXiv:2007.08123). The goal of the paper is to combine two different and unrelated numerical scores of the same items such as the skiing speed and shooting accuracy of a group of biathletes. Biathlons do this by using an arbitrary conversion factor to penalize skiing time based on shooting misses (essentially, adding the converted scores from the two parts of the sport) but instead some other sports multiply the ranks of the athletes within each discipline. So if you got, say, fifth in shooting but second in skiing, your overall score would be ten. My paper studies how quickly you can find the new winner after changing the score of a single competitor or by adding or removing a competitor in a sport using this system.

We can represent a set of items or group of athletes as points in the plane, whose coordinates are their ranks (not their raw scores). Then an update to the data that lies outside both the horizontal and vertical range of these points doesn’t change their relative positions: it might change their ranks, but all in the same way. So for these updates, the signed bounding box area minimization diagram stays unchanged. Because the bounding box area is just the product of ranks, we can use this diagram to quickly look up the winner among these shifted points. The overall strategy of the data structure in my paper is to divide the input data into smaller subsets and maintain their diagrams in such a way that most diagrams stay unchanged, and only a few need rebuilding, after each update. Dividing into more subsets reduces the rebuilding time, because fewer input items will belong to rebuilt diagrams, but increases the query time, because you have to query more diagrams. The \(O(\sqrt{n\log n})\) update time for the data structure in the paper comes from choosing the optimal tradeoff between these two terms of the total time.

There are other applications for this sort of rank aggregation beyond athletics; see the paper for details.

Because CCCG is online this year, I also have a video talk prepared, but it’s not yet online; I’ll post a link later. In the meantime, registration for CCCG is free this year, with a deadline of July 25, and enables both early access to the videos and access to the Q&A sessions with each speaker at the conference itself.

(Discuss on Mastodon)