Abrahamsen, Mikkel ;
Thorup, Mikkel
Finding the Maximum Subset with Bounded Convex Curvature
Abstract
We describe an algorithm for solving an important geometric problem arising in computeraided 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 simplyconnected set of points P in the plane such that the boundary of P is a curvilinear polygon consisting of n line segments and circular arcs of arbitrary radii, compute the maximum subset Q of P consisting of simplyconnected 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 rightcurvature 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 PestovIonin 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' is a subset of Q.
BibTeX  Entry
@InProceedings{abrahamsen_et_al:LIPIcs:2016:5896,
author = {Mikkel Abrahamsen and Mikkel Thorup},
title = {{Finding the Maximum Subset with Bounded Convex Curvature}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {4:14:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5896},
URN = {urn:nbn:de:0030drops58960},
doi = {10.4230/LIPIcs.SoCG.2016.4},
annote = {Keywords: planar computational geometry, bounded curvature, pocket machining}
}
2016
Keywords: 

planar computational geometry, bounded curvature, pocket machining 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 