Treffer: Two equivalent measures on weighted hypergraphs

Let H = (N, E, w) be a hypergraph with a node set N = {0, 1,..., n - 1}, a hyperedge set E ⊂ 2N, and real edge-weights w(e) for e E. Given a convex n-gon P in the plane with vertices x0, x1,... xn-1 which are arranged in this order clockwisely, let each node i e N correspond to the vertex xi and define the area Ap(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0≤i < j<k≤n - 1, a convex three-cut C(i, j, k) of N is {{i,.... j - 1), {j,..., k- 1), {k,...n - 1.0,...,i- 1}} and its size CH(i, j, k) in H is defined as the sum of weights of edges e ∈ E such that e contains at least one node from each of {i...., j - 1}, {j.... k - 1) and {k n - 1, 0,..., i - 1}. We show that the following two conditions are equivalent: • AP(H)≤AP(H') for all convex n-gons P. • CH(i, j, k) ≤cH'(i, j, k) for all convex three-cuts C(i, j,k). From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H' satisfy AP(H) ≤ AP(H') for all convex n-gons P is immediately obtained.