Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions (Q5919112)

The authors present efficient algorithms to compute the radius, diameter, incenter, circumcenter, width, \(k\)-dimensional minimum enclosing cylinder, and minimum stabbing sphere for convex polyhedral distance function, real convex polyhedral offset distance function, and normalized convex polyhedral offset distance function in plane and in \(\mathbb{R}^d\) for several types of inputs (convex polygon, convex polyhedron). The discussed problems are generalized to a set of points and to a set of convex polyhedra. The constraint versions are also considered. Computational complexity for solving the problems and obtaining an optimal solution is shown based on the size of input data, the size of distance function, and the size of constraint region. The authors give definitions of the radius, diameter, and other quantities as well as of all types of distance functions, introduce the problems that they solve, formulate them as linear programming problems, and present algorithms to solve the resulting problems optimally and efficiently.