Middlebury College
Department of Computer Science Seminar
Approximating a Polygonal Path using a Minimum Number of Circular Arcs of Biarcs
Scot Drysdale
Computer Science Professor
Dartmouth College
Tool paths for numerically-controlled cutting machines are usually represented as a series of line segments or circular arcs. Replacing a polygonal path by a series of arcs or biarcs (pairs of arcs with a common tangent where they join) can lead to smaller tool-path descriptions and smoother cuts. Researchers have invented heuristic algorithms for approximating a polygonal path by a series of arcs or biarcs, but it is not known how close these algorithms come to minimizing the number of arcs used in the approximation.
We present an algorithm that approximates a polygonal path by a minimum number of circular arcs while staying within a tolerance region and meeting other restrictions. The algorithm takes O(n2logn) time in the worst case, but in practice is likely to be closer to O(nlogn) time. We present a similar algorithm for approximating a polygonal path by biarcs that has the same asymptotic run time.
Friday, May 4, 2007
12:30 p.m. to 1:15 p.m.
McCardell Bicentennial Hall 538
Lunch will be provided at 12:15 p.m.
All are welcome to attend
This event is sponsored by the Computer Science Department.