Robust Free Space Computation for Curved Planar Bodies

We present a free space computation algorithm for two planar bodies bounded by line segments and circular arcs. The computational complexity is O(((mn)²+k)log(mn)) with m and n the number of boundary curves of the two bodies, and with k the number of configurations with three pairs of curves in contact. Although k is in O((mn)³), mild input restrictions reduce it to O(mn). We develop a robust implementation that is accurate, is fast, and handles degenerate input.