Growth Function of Halfspaces (2D)

Problem

Return the growth function of oriented halfspaces (lines) in two dimensions for n points in general position:

m(0) = 1, m(n) = n^2 - n + 2 for n >= 1

The quadratic growth mirrors the VC dimension of 3.

Hint

At n = 3 all eight dichotomies are realizable, but not at n = 4.

case 1

in: [0]

expected: 1

case 2

in: [1]

expected: 2

case 3

in: [2]

expected: 4

case 4

in: [3]

expected: 8

case 5

in: [10]

expected: 92

Starter codePython

def growth_function_halfspaces_2d(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor