Bisect circle for a balanced set of points

Problem1

$S$ is a set of $n$ points on the unit circle. No two points in $S$ lies on the same diagonal. Find a line that passes through the origin that divide the unit circle into two open semicircles, such that each piece have the same number of points in $S$ .

A harder version of this problem is Problem 1 in UIUC’s 1995 Fall Theory Qual. Let $C$ be the unit circle. The angle made by the lines and the $x$ -axis uniquely defines the line. Let the line pass through the origin with an angle $θ$ be $l_{θ}$ . Let $C (a, b) = \cup_{θ \in (a, b)} l_{θ} \cap C$ , $L$ is the semicircle below the $x$ -axis, $U$ is the semicircle above the $x$ -axis. $U (a, b)$ and $L (a, b)$ are define the same way as $C (a, b)$ .

We can solve this problem in $O (n)$ time by reducing it to a somewhat more general problem.

Problem2

Given two arcs $L (a, b)$ and $U (a, b)$ and a set of points $S$ on lying on the two arcs. $∣ S \cap L (a, b) ∣ \geq k$ and $∣ S \cap U (a, b) ∣ \leq k$ . $∣ l_{θ} \cap S ∣ \leq 1$ for all $θ \in (a, b)$ . Find a $l_{θ}$ , such that $θ \in (a, b)$ and $∣ S \cap (L (a, θ) \cup U (θ, b)) ∣ = k$ in $O (∣ S ∣)$ time.

Let’s consider an algorithm that returns line $l_{θ}$ be $p a r t i t i o n (S, a, b, k)$ .

Such a line must exist. Proof left as an exercise to the reader.

Note if we can solve this problem. We just need to rotate the circle so the points in the upper semicircle is at most the number of points in the lower semicircle, and then compute $p a r t i t i o n (S, 0, π, n /2)$ .

Let’s consider how to compute $p a r t i t i o n (S, a, b, k)$ . First, note for any line, we can decide the number of points in the intersection of constant number of half planes in linear time. This allow us to do cardinality computations of points lying on some arc in linear time.

We can find the $i$ th point on an arc from the left by using a linear time selection algorithm.

If the lower arc contains more than $2 k$ points, find the $k$ th point from the left in the lower arc. Assume it intersects $l_{θ}$ . We return $p a r t i t i o n (S \cap C (a, θ), a, θ, k - ∣ S \cap U (a, θ) ∣)$ .

So we are only dealing with the case where the lower arc contains less than $2 k$ points. We find the $k /2$ th point from the left in the lower arc. Assume it intersects $l_{θ}^{'}$ , and let $θ = θ^{'} + ϵ$ for a small enough epsilon(which would be apparent how small it has to be, and it can be found in linear time also.). Let $(u, v, y, x) = (∣ S \cap L (a, θ) ∣, ∣ S \cap L (θ, b) ∣, ∣ S \cap U (a, θ) ∣, ∣ S \cap U (θ, b) ∣)$ . Note $u = k /2$ and $u + x = ∣ S \cap (L (a, θ) \cup U (θ, b)) ∣$ , $x + y \leq k$ , $u + v \geq k$ .

If $u + x = k$ , then we are done, return $l_{θ}^{'}$ .
If $u + x > k$ , then return $p a r t i t i o n (S \cap C (a, θ), a, θ, k - x)$ .
If $u + x < k$ , then return $p a r t i t i o n (S \cap C (θ, b), θ, b, k /2)$ .

One can verify it’s valid to call the partition functions, namely the precondition for the number of points lower arc and upper arc is satisfied. There might be some off by one error somewhere. But the general idea is there.

When $k$ is small enough we solve the problem by brute force.

Every time we nest a $p a r t i t i o n$ call, we spend linear time on the current point sets, then we call the function again but with a point set of size a constant times smaller. This give us the linear time algorithm required.

This is actually a special case of the ham sandwich problem in $2$ D. There are $n$ red points and $m$ blue points on the plane. Find a line such that it divides the plane into two half-planes, so the interior of each half-plane contains at most $⌊ n /2 ⌋$ red points and $⌊ m /2 ⌋$ blue points. So our problem is when the red point is purely the origin.

Posted by Chao Xu on 2014-03-27.

Tags: Algorithm.