Efficient Algorithms for Approximating the Centroids of Monotone Directions in a Polyhedron
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We present efficient algorithms for computing centroid directions for each of the three types of monotonicity in a polyhedron: strong, weak, and directional monotonicity, which can be used for optimizing directions in many 3D manufacturing processes. Strongly- and directionally-monotone directions are the poles of great circles separating a set of spherical polygons on the unit sphere, the centroids of which are shown to be obtained by applying the previous result for determining the maximum intersection of the set of their dual spherical polygons. Especially in this paper, we focus on developing an efficient method for approximating the weakly-monotone centroid, which is the pole of one of the great circles intersecting a set of spherical polygons on the unit sphere. The original problem is approximately reduced into computing the intersection of great bands for avoiding complicated computational complexity of non-convex objects on the unit sphere, which can be realized with practical linear-time operations.
Abstract
We present efficient algorithms for computing centroid directions for each of the three types of monotonicity in a polyhedron: strong, weak, and directional monotonicity, which can be used for optimizing directions in many 3D manufacturing processes. Strongly- and directionally-monotone directions are the poles of great circles separating a set of spherical polygons on the unit sphere, the centroids of which are shown to be obtained by applying the previous result for determining the maximum intersection of the set of their dual spherical polygons. Especially in this paper, we focus on developing an efficient method for approximating the weakly-monotone centroid, which is the pole of one of the great circles intersecting a set of spherical polygons on the unit sphere. The original problem is approximately reduced into computing the intersection of great bands for avoiding complicated computational complexity of non-convex objects on the unit sphere, which can be realized with practical linear-time operations.
참고문헌 (16)
- J. Ha, "Characterization of polyhedron monotonicity", Computer-Aided Design, 38(1), pp.48~54 (2006)
- J. Ha, "Approximating centroids for the maximum intersection of spherical polygons", Computer-Aided Design, 37(8), pp.783~790 (2005)
- G. Toussaint, "Computational Geometry" (1985), Elsevier Science
- S. C. L. L. Chen, "Separating and intersecting spherical polygons: computing machinability on three- four- and five-axis numerically controlled machines", ACM Tr. on Graphics, 12(4), pp.305~326 (1993)
- Lin-Lin Chen, "Parting directions for mould and die design", Computer-Aided Design, 25(12), pp.762~768 (1993)
- E. Welzel, "Smallest enclosing disks (balls and ellipsoids)", New Results and New Trends in Computer Science, 555, pp.359~370 (1991), Springer Lecture Notes in Computer Science
- N. Megiddo, "Linear programming in linear time when the dimension is fixed", Journal of ACM, 31(1), pp.114~127 (1984)
- M. Dyer, "Linear time algorithms for two-and three-variable linear programs", SIAM. Journal on Computing, 13(1), pp.31~45 (1984)
- R. Seidel, "Small-dimensional linear programming and convex hulls made easy", Discrete Computing Geometry, 6(5), pp.423~434 (1991)
- T. Woo, "Visibility maps and spherical algorithms", Computer Aided Design, 26(1), pp.6~16 (1994)
- G. Toussaint, "Computing largest empty circles with location constraints", International Journal of Computer and Information Sciences, 12(5), pp.347~358 (1983)
- J. G. Gan, "Spherical maps: their construction, properties, and approximation", ASME J. Mechanical Design, 116, pp.357~363 (1994)
- [URL]
- [URL]
- [URL]
- [URL]