round_polytope: Apply rounding to a convex polytope (H-polytope, V-polytope...

In volesti: Volume Approximation and Sampling of Convex Polytopes

Apply rounding to a convex polytope (H-polytope, V-polytope or a zonotope)

Description

Given a convex H or V polytope or a zonotope as input this function brings the polytope in rounded position based on minimum volume enclosing ellipsoid of a pointset.

Usage

round_polytope(P, settings = list())

Arguments

P

A convex polytope. It is an object from class (a) Hpolytope or (b) Vpolytope or (c) Zonotope.

settings

Optional. A list to parameterize the method by the random walk. random_walk The random walk to sample uniformly distributed points: (a) 'CDHR' for Coordinate Directions Hit-and-Run, (b) 'RDHR' for Random Directions Hit-and-Run or (c) 'BiW' for Billiard walk. The default random walk is 'CDHR' for H-polytopes and 'BiW' for the rest of the representations. walk_length The walk length of the random walk. The default value is 10 + 10d for 'CDHR' or 'RDHR' and 2 for 'BiW'. seed Optional. A fixed seed for the number generator.

Value

A list with 4 elements: (a) a polytope of the same class as the input polytope class and (b) the element "T" which is the matrix of the inverse linear transformation that is applied on the input polytope, (c) the element "shift" which is the opposite vector of that which has shifted the input polytope, (d) the element "round_value" which is the determinant of the square matrix of the linear transformation that is applied on the input polytope.

References

I.Z.Emiris and V. Fisikopoulos, “Practical polytope volume approximation,” ACM Trans. Math. Soft., 2018.,

Michael J. Todd and E. Alper Yildirim, “On Khachiyan’s Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids,” Discrete Applied Mathematics, 2007.

Examples

# rotate a H-polytope (2d unit simplex)
A = matrix(c(-1,0,0,-1,1,1), ncol=2, nrow=3, byrow=TRUE)
b = c(0,0,1)
P = Hpolytope(A = A, b = b)
listHpoly = round_polytope(P)

# rotate a V-polytope (3d unit cube) using Random Directions HnR with step equal to 50
P = gen_cube(3, 'V')
ListVpoly = round_polytope(P)

# round a 2-dimensional zonotope defined by 6 generators using ball walk
Z = gen_rand_zonotope(2,6)
ListZono = round_polytope(Z)

volesti documentation built on Sept. 19, 2023, 5:08 p.m.