Counting the number of polygons containing origin in 2D

Question

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.

Answer 1

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.)