Maximal intersection of spherical polygons by an arc with applications to 4-axis machining
✍ Scribed by Kai Tang; Yong-Jin Liu
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 737 KB
- Volume
- 35
- Category
- Article
- ISSN
- 0010-4485
No coin nor oath required. For personal study only.
✦ Synopsis
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 # 2p; 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 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 upperbound 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.