Sorting Circles

In today's post, we are going to consider a simple problem, and do it the hard way.

The problem is this: We are given a set of circles in the 2D plane. These circles are defined by the X and Y coordinates of their center, and by the square of their radius, Q = r². All three of these values are rational numbers. We are then tasked to sort the circles according to the following order: circle 1 comes before circle 2 if the bottom of circle 1 is above the bottom of circle 2. As an example, the following circles are in the order we want:

The easy way to do this problem is straightforward. The bottom of each circle is the point (X, Y - sqrt(Q)), a point that is not necessarily rational. Fortunately, the irrational numbers are well-ordered, so we can still sort the circles by this bottom point, from largest to smallest Y-coordinate

As I mentioned at the start, however, we are not going to solve this problem the easy way. We wish to remain in the domain of rational numbers, and so we will ban the use of the square root function when considering our solution.

I am sure this decision will raise a few questions, which I will attempt to address:

Why are all three values rational? Behind the scenes, these circles are defined as the circle containing three distinct points, as discussed in a previous post. Each of these three points are specified in rational coordinates, and the equation derived for their circumcircle shows that the center of the circle is also a rational point. Additionally, the square of the distance between two points is also a rational number. The actual distance may not be rational, however. If you want a counterexample, take the three points (-1, 1), (1, 1), and (1, -1), which are all a distance of sqrt(2) from the origin.

Why is the squared radius denoted Q? Q stands for quadrance, a concept I borrowed from an interesting looking Wikipedia page about 'rational trigonometry'.

What do you have against irrational numbers? Theoretically, nothing. Practically, they are anathema to a computer, which can only truly work with integers. Floating-point numbers are a conceit that trades accuracy for range, and if you aren't careful, you will get the wrong answer due to accumulated round-off errors, and all of your numerical tests are studded with epsilons that turn y = c into |y - c| ≤ 1.0^-6 for some arbitrarily-chosen exponent. If you use a solid rational number library, your answers will be guaranteed to be correct with knife-edge precision.

Your proposed rational number library will be slower. First, that's not a question. Second, will it? Probably, but I will practically guarantee that you've made this statement as a knee-jerk reaction; more than half of all statement of 'x is slower' being used to justify a particulary technical approach are based on no actual data. Third, who cares? If it's twice as slow, and the slower algorithm still finishes in 10ms, then doubling its speed isn't going to make your user any happier. We're not writing a real-time operating system today. Correctly getting the right answer is our aim, not quickly getting a wrong answer.

Exactly why are you sorting circles this way? The reason why will have to wait for a future post. For now, let it be sufficient that this is a problem of mathematics, and the search for an answer is of value, not an application of the answer.

What is the answer? Give it some thought. I'll tell you in the next post.