2

I was working on the following problem. Given n points on a circle, where a point can be specified by its angle from the vertical, how does one find a diameter of the circle such that the number of points on the left equals the number of points on the right (points on the diameter itself are either ignored, or counted once on both sides, it doesn't matter) in O(n) time?

I'm given the additional convenience that the angles are given in increasing order $0 \le \theta_1 \le \theta_2 ... \le \theta_n \le 2 \pi$

Attempts to Not Repeat Whats Already Been Done:

I found this question: https://stackoverflow.com/questions/19709823/find-a-bisecting-diameter

But it was unanswered and the only comment was a generic reference to comparison based median selection.

Work So Far:

So before attempting to build an $O(n)$ algorithm I figured it would be wise to just build AN algorithm. In the event that $n$ is odd, it's clear the bisecting diameter would have to pass through one of the points so consider all points (each has a diameter that passes through it) and select the one that is bisecting. The total cost then will be $n C(n)$ where $C(n)$ is the cost of checking if a particular diameter bisects.

Something to observe is that since the angles are sorted, we can make a circular linked list of angles $\theta_1 ... \theta_n$ and maintain a pointer at the angle $\theta_k$ which corresponds to the $k^{th}$ bisecting diameter we are checking, and then a point to the angle $\theta_{n(k)}$ which is the closest angle that is more than $\pi$ radians away (both measured counter clockwise) from $\theta_k$ (the pointers maintain a count that lets us compute their distance in $O(1)$ time (which also corresponds to the number of points they share (we aim to get a distance of n/2)) We observe that the pointer for $\theta_{n(k)}$ can never cross the pointer for $\theta_k$, and therefore in the worst case $\theta_k$ can get right behind $\theta_k$ and then update once for every check of $\theta_k$ thus we have worst case $2n$ changes of $\theta_{n(k)}$, and $n$ changes to $\theta_k$ and therefore this algorithm has worst care running time $O(n)$.

For the case of $n$ being even I remain a bit lost. So far what I have is I can easily remove a point and find a bisecting diameter using the previous algorithm. Then reintroduce that point, and then rotate the diameter by some miniscule $\epsilon > 0$ to balance the two sides?

My dislike of this strategy is that it feels indirect. And furthermore I have no information on how close the $\theta$ can be to each other, (perhaps they have $O(n^2)$ significant figures!). So this algorithm would be sensitive to the form of my data.

Community
  • 1
Sidharth Ghoshal
  • 16,771

1 Answers1

1

You have the right idea for both cases: imagine you take diameter and color both radii with a different color (like a compass) so that the radius with angle $\theta$ is blue and that with angle $\pi + \theta$ is red.

Now you start from some $\theta_0$ that does not hit any points (for instance the average of the angle of the first two sorted points) and count the number of "left" and "right" points.

Now sweep the diameter from $\theta = \theta_0$ to $\theta = \theta_0 + \pi$. At each step of the sweep, one of three possibilities will occur:

  1. The blue radius hits a point first. Decrement the number of points on the "left" and check if both sides are equal (this covers the odd case). Increment the number of points on the "right" and check again if both sides are now equal.

  2. The red radius hits a point first. Do the same as the above case but first decrement the "right" counter, etc.

  3. Both radii hit a point at exactly the same time. The number of points on each side remains unchanged.

Since at $\theta = \theta_0 + \pi$ the number of points on the left and right will have swapped, and each step above changed the difference in the number of points by one at a time, it is guaranteed that the number of points on both sides will be equal at some point during the algorithm.

user7530
  • 49,280