Suppose we have n points in 2D space in convex position. There are precisely choose(n, k) different convex k-gons (non-degenerate). Is there any existing algorithm that runs in O(n log n) time (for a fixed k) which counts the number of polygons containing the origin?
I tried to look for any such algorithms in the literature, but only managed to find an algorithm for k=3.
Here is a sweep line algorithm.
First, count up polygons. Then sweep a line around, removing polygons not containing the origin when the polygon is fully in view, then has its first point removed.
import math
def choose (n, m):
# Special case this to avoid division by zero.
if n < m:
return 0
else:
answer = 1
for i in range(m):
answer = (answer * (n-i)) // (i+1)
return answer
# I assume that points are (x, y) pairs here.
def count_poly_containing_origin (k, points):
# Start with total number of polygons, subtract those without origin.
polys = choose(len(points), k)
# Convert ones not at origin to angle with -pi < angle <= pi
angles = []
for x, y in points:
if x == 0 and y == 0:
pass # I'm assuming closed polygons. Have this, have origin.
else:
angles.append(math.atan2(x, y))
angles = sorted(angles)
# We are going to sweep a line around. We will add each point when we
# see it, and remove it math.pi later. When we remove the point, we
# subtract off how many polygons it is in that do not contain the origin.
#
#
# i represents what we will remove next. j represents what we will add
# next, selected is how many points are currently selected.
#
# We start nothing selected, added, or removed.
i = j = selected = 0
while i < len(angles):
if i <= j:
if angles[j] < angles[i] + math.pi:
# add point
selected += 1
j += 1
# Do we need to wraparound?
if j == len(angles):
j = 0
else:
# remove point
selected -= 1
i += 1
# Remove the polygons containing angles[i] and not the origin.
polys -= choose(selected, k-1)
else:
if angles[j] < angles[i] - math.pi:
# add point
selected += 1
j += 1
else:
# remove point
selected -= 1
i += 1
# Remove the polygons containing removed point and not the origin.
polys -= choose(selected, k-1)
return polys
For fixed k
this is a O(n log(n))
algorithm. For large k
the bottleneck is repeatedly calculating choose(m, k-1)
for the subtraction. That can be sped up by creating a lookup table for it in O(n)
. (Left as an exercise for the reader.)