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

DOI10.1016/j.dam.2020.10.021zbMath1484.65041OpenAlexW3109611887MaRDI QIDQ5919112

Swami Sarvottamananda, Sandip Das, Ayan Nandy

Publication date: 21 October 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.10.021

zbMATH Keywords

computational complexitywidthdiameterradiusgeometric optimizationcircumcenterincenterlinear programming problemminimum enclosing cylinderconvex polyhedral distance functionminimum stabbing sphere

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55) Linear programming (90C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polyhedra and polytopes; regular figures, division of spaces (51M20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) General theory of distance geometry (51K05)

Related Items

A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes, A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes

Cites Work

• Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex Constraints
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance Function
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• Voronoi diagrams for convex polygon-offset distance functions