计算二维中包含原点的多边形数量

Question

假设我们在 2D 空间中有 n 个处于凸位置的点。精确地选择（n，k）个不同的凸k边形（非退化）。是否有任何现有算法可以在 O(n log n) 时间内运行（对于固定 k）来计算包含原点的多边形数量？

我试图在文献中寻找任何此类算法，但只找到了 k=3 的算法。

Answer 1

这是一个扫线算法。

首先，计算多边形数。然后扫一圈线，当多边形完全处于视图中时删除不包含原点的多边形，然后删除其第一个点。

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

对于固定

k

，这是一个

O(n log(n))

算法。对于较大的

k

，瓶颈在于重复计算

choose(m, k-1)

进行减法。可以通过在

O(n)

中为其创建查找表来加快速度。 （留给读者作为练习。）