The Erdős--Nagy theorem and its ramifications

DOI10.1016/J.COMGEO.2004.12.005MaRDI QIDQ2486085zbMATH OpenOpenAlexFDO

Authors Godfried Toussaint

Publication date 5 August 2005

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2004.12.005

zbMATH Keywords

computational geometryconvex hullconvexificationcurve inflationdeflationflipflipturnknot theorymolecular reconfigurationpivotpolygonal linkagespolygonspolymer physicsroboticsself-avoiding walks

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The authors give the historical overview the necessity to solve the convexification problem which kept appearing in many areas of research. The convexification problem lies in the reconfiguration of a non convex polygon to a convex one. The basic solution was proposed by Paul Erdős and Béla Nagy. Erdős conjectured that the simple (non self-crossing) polygon would become convex after a finite number of simultaneous flipping of all the pockets of the polygon [cf. \textit{R. E. Gaines, P. Erdős, H. D. Grassman, V. Thebault}, and \textit{W. P. Ubinski}, Amer. Math. Monthly 42, No.~10, 625--627 (1935)]. Nagy proved that the polygon would become convex after a finite number of separate flipping of only one pocket at each step [cf. \textit{P. Erdős} and \textit{B. de Sz.-Nagy}, ibid. 46, No.~3, 176--177 (1939)]. The stronger version of the Erdős-Nagy theorem relates to the convexification of non-simple (self crossing) polygons. In the article, the proof of Erdős-Nagy theorem as well as the proofs of various stronger versions of the Erdős-Nagy theorem are given; e.g. convexification of self crossing polygon while keeping a specified edge fixed, convexification of star-shaped equilateral polygon, convexification of spatial polygons, etc. In conclusion, the authors also mention several open problems of convexification which have not been satisfactorily solved yet.

Recommendations

• scientific article; zbMATH DE number 866052
• scientific article; zbMATH DE number 1877248
• All polygon flip finitely\dots right?
• Chord-stretched convex versions of planar curves with self-intersections
• Convexification of polygons by flips and by flipturns

Cites work

• A chord-stretching map of a convex loop is an isometry
• A linear algorithm for finding the convex hull of a simple polygon
• A new class of stuck unknots in \(\text{Pol}_6\)
• Chord-stretched convex versions of planar curves with self-intersections
• Computational Geometry in C
• Convexification of polygons by flips and by flipturns
• Flipturning Polygons
• scientific article; zbMATH DE number 3128796 (Why is no real title available?)
• scientific article; zbMATH DE number 3158065 (Why is no real title available?)
• scientific article; zbMATH DE number 4062154 (Why is no real title available?)
• scientific article; zbMATH DE number 4068937 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3507537 (Why is no real title available?)
• scientific article; zbMATH DE number 739035 (Why is no real title available?)
• scientific article; zbMATH DE number 1552835 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• scientific article; zbMATH DE number 1877248 (Why is no real title available?)
• scientific article; zbMATH DE number 866052 (Why is no real title available?)
• KNOTTING OF REGULAR POLYGONS IN 3-SPACE
• Locked and unlocked polygonal chains in three dimensions
• More classes of stuck unknotted hexagons
• NONTRIVIAL EMBEDDINGS OF POLYGONAL INTERVALS AND UNKNOTS IN 3-SPACE
• On-line construction of the convex hull of a simple polyline
• Partial inflation of closed polygons in the plane
• Polygons needing many flipturns
• Reconfiguring closed polygonal chains in Euclidean \(d\)-space
• Reconfiguring convex polygons
• Self-avoiding random loops
• Simple polygons with an infinite sequence of deflations
• Simple Proofs of a Geometric Property of Four-Bar Linkages
• Smooth Curves of Constant width and Transnormality
• Stretching chords of space curves
• The pivot algorithm and polygons: results on the FCC lattice
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
• The symplectic geometry of polygons in Euclidean space

Cited in

(10)

• On the stability of the polygonal isoperimetric inequality
• Chord-stretched convex versions of planar curves with self-intersections
• All polygon flip finitely\dots right?
• Approximate Shortest Paths in Polygons with Violations
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• Deflating the Pentagon
• An ergodic algorithm for generating knots with a prescribed injectivity radius
• The generation of random equilateral polygons
• Simple polygons with an infinite sequence of deflations
• On convexification of polygons by pops

This page was built for publication: The Erdős--Nagy theorem and its ramifications

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