Finding the maximum subset with bounded convex curvature

TY - GEN

T1 - Finding the maximum subset with bounded convex curvature

AU - Abrahamsen, Mikkel

AU - Thorup, Mikkel

N1 - Conference code: 32

PY - 2016/6/1

Y1 - 2016/6/1

N2 - We describe an algorithm for solving an important geometric problem arising in computer-aided manufacturing. When machining a pocket in a solid piece of material such as steel using a rough tool in a milling machine, sharp convex corners of the pocket cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a tool path that maximizes the use of the rough tool. Mathematically, this boils down to the following problem. Given a simply-connected set of points P in the plane such that the boundary ∂P is a curvilinear polygon consisting of n line segments and circular arcs of arbitrary radii, compute the maximum subset Q ⊆ P consisting of simply-connected sets where the boundary of each set is a curve with bounded convex curvature. A closed curve has bounded convex curvature if, when traversed in counterclockwise direction, it turns to the left with curvature at most 1. There is no bound on the curvature where it turns to the right. The difference in the requirement to left- and right-curvature is a natural consequence of different conditions when machining convex and concave areas of the pocket. We devise an algorithm to compute the unique maximum such set Q. The algorithm runs in O(n log n) time and uses O(n) space. For the correctness of our algorithm, we prove a new generalization of the Pestov-Ionin Theorem. This is needed to show that the output Q of our algorithm is indeed maximum in the sense that if Q′ is any subset of P with a boundary of bounded convex curvature, then Q′ ⊆ Q.

AB - We describe an algorithm for solving an important geometric problem arising in computer-aided manufacturing. When machining a pocket in a solid piece of material such as steel using a rough tool in a milling machine, sharp convex corners of the pocket cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a tool path that maximizes the use of the rough tool. Mathematically, this boils down to the following problem. Given a simply-connected set of points P in the plane such that the boundary ∂P is a curvilinear polygon consisting of n line segments and circular arcs of arbitrary radii, compute the maximum subset Q ⊆ P consisting of simply-connected sets where the boundary of each set is a curve with bounded convex curvature. A closed curve has bounded convex curvature if, when traversed in counterclockwise direction, it turns to the left with curvature at most 1. There is no bound on the curvature where it turns to the right. The difference in the requirement to left- and right-curvature is a natural consequence of different conditions when machining convex and concave areas of the pocket. We devise an algorithm to compute the unique maximum such set Q. The algorithm runs in O(n log n) time and uses O(n) space. For the correctness of our algorithm, we prove a new generalization of the Pestov-Ionin Theorem. This is needed to show that the output Q of our algorithm is indeed maximum in the sense that if Q′ is any subset of P with a boundary of bounded convex curvature, then Q′ ⊆ Q.

U2 - 10.4230/LIPIcs.SoCG.2016.4

DO - 10.4230/LIPIcs.SoCG.2016.4

M3 - Article in proceedings

SN - 978-3-95977-009-5

T3 - Leibniz International Proceedings in Informatics

BT - 32nd International Symposium on Computational Geometry (SoCG 2016)

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Symposium on Computational Geometry (SoCG 2016)

Y2 - 14 June 2016 through 18 June 2016

ER -