Linear programming in R^ 3 and the skeleton and largest incircle of a convex polygon

DOI10.1016/0898-1221(87)90008-3MaRDI QIDQ1102184zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1987

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(87)90008-3

zbMATH Keywords

convex polygongeometrical problemlargest circle

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Review text

The geometrical problem of constructing the largest circle inscribed in a (given) convex polygon is solved in O(n) time. This problem is related to the construction of the skeleton of the polygon, which is shown to be accomplishable in O(n log n) time.

Recommendations

• Three problems about simple polygons
• Linear algorithm to find the largest intriangles of a planar convex polygon
• scientific article; zbMATH DE number 2169076
• Finding largest rectangles in convex polygons
• The orthogonal convex skull problem

Cites work

• Continuous Skeletons from Digitized Images
• Finding the intersection of n half-spaces in time O(n log n)
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems

Cited in

(3)

• The orthogonal convex skull problem
• scientific article; zbMATH DE number 3988128 (Why is no real title available?)
• Shakedown of elastic-perfectly plastic materials with temperature-dependent elastic moduli

This page was built for publication: Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102184)