The Art Gallery Guardian

Bisect circle for a balanced set of points


Problem1

SS is a set of nn points on the unit circle. No two points in SS 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 SS.

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

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

Problem2

Given two arcs L(a,b)L(a,b) and U(a,b)U(a,b) and a set of points SS on lying on the two arcs. SL(a,b)k|S\cap L(a,b)|\geq k and SU(a,b)k|S\cap U(a,b)|\leq k. lθS1|l_\theta\cap S|\leq 1 for all θ(a,b)\theta\in(a,b). Find a lθl_\theta, such that θ(a,b)\theta\in(a,b) and S(L(a,θ)U(θ,b))=k|S\cap (L(a,\theta)\cup U(\theta,b))|=k in O(S)O(|S|) time.

Let's consider an algorithm that returns line lθl_\theta be partition(S,a,b,k)partition(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 partition(S,0,π,n/2)partition(S,0,\pi,n/2).

Let's consider how to compute partition(S,a,b,k)partition(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 iith point on an arc from the left by using a linear time selection algorithm.

If the lower arc contains more than 2k2k points, find the kkth point from the left in the lower arc. Assume it intersects lθl_\theta. We return partition(SC(a,θ),a,θ,kSU(a,θ))partition(S\cap C(a,\theta),a,\theta,k-|S\cap U(a,\theta)|).

So we are only dealing with the case where the lower arc contains less than 2k2k points. We find the k/2k/2th point from the left in the lower arc. Assume it intersects lθl_\theta', and let θ=θ+ϵ\theta=\theta'+\epsilon 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)=(SL(a,θ),SL(θ,b),SU(a,θ),SU(θ,b))(u,v,y,x) = (|S\cap L(a,\theta)|,|S\cap L(\theta,b)|,|S\cap U(a,\theta)|,|S\cap U(\theta,b)|). Note u=k/2u=k/2 and u+x=S(L(a,θ)U(θ,b))u+x = |S\cap (L(a,\theta)\cup U(\theta,b))|, x+ykx+y\leq k, u+vku+v\geq k.

  • If u+x=ku+x = k, then we are done, return lθl_\theta'.
  • If u+x>ku+x > k, then return partition(SC(a,θ),a,θ,kx)partition(S\cap C(a,\theta),a,\theta,k-x).
  • If u+x<ku+x < k, then return partition(SC(θ,b),θ,b,k/2)partition(S\cap C(\theta,b),\theta,b,k/2).
Bisect Circle Example
Bisect Circle Example

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 kk is small enough we solve the problem by brute force.

Every time we nest a partitionpartition 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 22D. There are nn red points and mm 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\lfloor n/2 \rfloor red points and m/2\lfloor m/2 \rfloor blue points. So our problem is when the red point is purely the origin.

Posted by Chao Xu on .
Tags: .