Maximal intersection of spherical polygons by an arc with applications to 4-axis machining
Published in Computer-Aided Design, 2003
Abstract: Many geometric optimization problems in CAD/CAM can be reduced to a maximal intersection problem on the sphere: given a set of $N$ simple spherical polygons on the unit sphere and a real number constant $L\le 2\pi$; find an arc of length $L$ on the unit sphere that intersects as many spherical polygons as possible. Past results can only solve this maximization problem for two very restricted special cases: the arc must be either a great circle or a semi-great circle. In this paper, a simple and deterministic algorithm based on domain partitioning is presented for solving this maximal arc intersection problem in the general case when the number $L$ is arbitrary. The algorithm is made possible by reducing the domain of the arcs to a continuous sub-space in $\mathbb{R}^2$ and then establishing a quotient space partitioning in this sub-space based on a congruence relation. The number of the constituting congruent sub-regions in this quotient space partitioning is shown to have an upper-bound $O(E^{3})$; where $E$ is the total number of edges on the polygons. The proposed algorithm has a worst-case upper bound $O(ME)$ on its running time, where M is an output-sensitive number and is bounded by $O(E^{3})$. Examples including two realistic tests for 4-axis NC machining are presented.
Recommended citation: Kai Tang, Yong-Jin Liu (2003) Maximal intersection of spherical polygons by an arc with applications to 4-axis machining. Computer-Aided Design, Vol. 35, No. 14, pp. 1269-1285, 2003.