{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T05:59:37Z","timestamp":1673589577060},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[1993,10]]},"abstract":"\n We consider the computation of an optimal workpiece orientation allowing the maximal number of surfaces to be machined in a single setup on a three-, four-, or five-axis numerically controlled machine. Assuming the use of a ball-end cutter, we establish the conditions under which a surface is machinable by the cutter aligned in a certain direction, without the cutter's being obstructed by portions of the same surface. The set of such directions is represented on the sphere as a convex region, called the\n visibility map<\/jats:italic>\n of the surface. By using the Gaussian maps and the visibility maps of the surfaces on a component, we can formulate the optimal workpiece orientation problems as geometric problems on the sphere. These and related geometric problems include finding a densest hemisphere that contains the largest subset of a given set of spherical polygons, determining a great circle that separates a given set of spherical polygons, computing a great circle that bisects a given set of spherical polygons, and finding a great circle that intersects the largest or the smallest subset of a set of spherical polygons. We show how all possible ways of intersecting a set of\n n<\/jats:italic>\n spherical polygons with\n v<\/jats:italic>\n total number of vertices by a great circle can be computed in\n O<\/jats:italic>\n (\n vn<\/jats:italic>\n log\n n<\/jats:italic>\n ) time and represented as a spherical partition. By making use of this representation, we present efficient algorithms for solving the five geometric problems on the sphere.\n <\/jats:p>","DOI":"10.1145\/159730.159732","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:00Z","timestamp":1027769340000},"page":"305-326","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Separating and intersecting spherical polygons"],"prefix":"10.1145","volume":"12","author":[{"given":"Lin-Lin","family":"Chen","sequence":"first","affiliation":[{"name":"National Taiwan Institute of Technology, Taipei, Taiwan"}]},{"given":"Shuo-Yan","family":"Chou","sequence":"additional","affiliation":[{"name":"National Taiwan Institute of Technology, Taipei, Taiwan"}]},{"given":"Tony C.","family":"Woo","sequence":"additional","affiliation":[{"name":"Univ. of Michigan, Ann Arbor"}]}],"member":"320","published-online":{"date-parts":[[1993,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187911"},{"key":"e_1_2_1_2_1","volume-title":"Notional Computer Conference, AFIPS Conference Proceedings. AFIPS, Arlington, Va., 589 596","year":"1975","unstructured":"BAUMC, ART, B. 1975 . A polyhedron representation for computer vision . In Notional Computer Conference, AFIPS Conference Proceedings. AFIPS, Arlington, Va., 589 596 . BAUMC, ART, B. 1975. A polyhedron representation for computer vision. In Notional Computer Conference, AFIPS Conference Proceedings. AFIPS, Arlington, Va., 589 596."},{"key":"e_1_2_1_3_1","unstructured":"BROWN K.Q. 1979.\n Geometric transformations for fast geometric algorithms\n . Ph.D. thesis Dept. of Computer Science Carnegie-Mellon Univ. Pittsburgh Pa. BROWN K.Q. 1979. Geometric transformations for fast geometric algorithms. Ph.D. thesis Dept. of Computer Science Carnegie-Mellon Univ. Pittsburgh Pa."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Symposium on Concurrent Engineering. ASME","year":"1992","unstructured":"CHEN I,. L., AND CHOV, S. Y. 1992 . Optima} parting directions by partial visibility . In Proceedings of the Symposium on Concurrent Engineering. ASME , New York.3 CHEN I,. L., AND CHOV, S. Y. 1992. Optima} parting directions by partial visibility. In Proceedings of the Symposium on Concurrent Engineering. ASME, New York.3"},{"issue":"2","key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1115\/1.2916945","article-title":"Computational geometry on the sphere for automated machining","volume":"114","year":"1992","unstructured":"CHEN, L. L., AND W(xL T. C. 1992 . Computational geometry on the sphere for automated machining . ASME J. Mech. Des. 114 , 2 , 288 - 295 . CHEN, L. L., AND W(xL T. C. 1992. Computational geometry on the sphere for automated machining. ASME J. Mech. Des. 114, 2, 288-295.","journal-title":"ASME J. Mech. Des."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set covering problem","volume":"4","year":"1979","unstructured":"CHVATAL V. 1979 . A greedy heuristic for the set covering problem . Math. Oper. Res. 4 , 3, 233 235. CHVATAL V. 1979. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 3, 233 235.","journal-title":"Math. Oper. Res."},{"key":"e_1_2_1_9_1","volume-title":"Algorithms in Combinatorial Geometry","author":"Rtr NNER","unstructured":"EDEI,SB Rtr NNER , H. 1987. Algorithms in Combinatorial Geometry . Springer-Verlag , New York . EDEI,SBRtrNNER, H. 1987. Algorithms in Combinatorial Geometry. Springer-Verlag, New York."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"EDELSI4RtrNNER H. GUIBAS L. J. AND SHARIR M. 1989. The upper envelope ofpiecewise linear functions: Algorithms and applications. Discr. Comput. Geom. 4 4 311 336 EDELSI4RtrNNER H. GUIBAS L. J. AND SHARIR M. 1989. The upper envelope ofpiecewise linear functions: Algorithms and applications. Discr. Comput. Geom. 4 4 311 336","DOI":"10.1007\/BF02187733"},{"key":"e_1_2_1_11_1","volume-title":"Computational Geometry for Design and Manufacture","unstructured":"F^ux, I. D., AND PRAY, M.J. 1979. Computational Geometry for Design and Manufacture . Halsted Press , New York . F^ux, I. D., AND PRAY, M.J. 1979. Computational Geometry for Design and Manufacture. Halsted Press, New York."},{"key":"e_1_2_1_12_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","unstructured":"GAREY, M. R., AND JOHNSON, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness , Freeman , San Francisco . GAREY, M. R., AND JOHNSON, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco."},{"issue":"4","key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/0196-6774(83)90013-5","article-title":"Finding the convex hull of a simple polygon","volume":"4","year":"1983","unstructured":"GRAHAM, R. L., AND Y^O, F.F. 1983 . Finding the convex hull of a simple polygon . J. Alg. 4 , 4 , 324 - 331 . GRAHAM, R. L., AND Y^O, F.F. 1983. Finding the convex hull of a simple polygon. J. Alg. 4, 4, 324-331.","journal-title":"J. Alg."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/282918.282923"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90136-1"},{"key":"e_1_2_1_16_1","volume-title":"Geometry and the Imagination","author":"Irr D.","unstructured":"HILBE Irr , D. , AND COHN- VOSSEN , S. 1952. Geometry and the Imagination . Chelsea, New York . HILBEIrr, D., AND COHN-VOSSEN, S. 1952. Geometry and the Imagination. Chelsea, New York."},{"key":"e_1_2_1_17_1","unstructured":"HOFFM~-N C.M. 1989. Geometric and Solid Modeling' An Introduction. Morgan Kaufmann San Mateo Calif. HOFFM~-N C.M. 1989. Geometric and Solid Modeling' An Introduction. Morgan Kaufmann San Mateo Calif."},{"issue":"1","key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","article-title":"The densest hemisphere problem","volume":"6","author":"Pgr F.P.","year":"1978","unstructured":"JOHNSON, D. S., AND Pgr . PARaT^, F.P. 1978 . The densest hemisphere problem . Theoret. Comput. Sci. 6 , 1 , 93 - 107 . JOHNSON, D. S., AND Pgr. PARaT^, F.P. 1978. The densest hemisphere problem. Theoret. Comput. Sci. 6, 1, 93-107.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_19_1","volume-title":"The Art of Computer Programming","unstructured":"KNUTH, D. E. 1968. The Art of Computer Programming . Vol. I , Fundamental Algorithms. Addison-Wesley , Reading, Mass. KNUTH, D. E. 1968. The Art of Computer Programming. Vol. I, Fundamental Algorithms. Addison-Wesley, Reading, Mass."},{"key":"e_1_2_1_20_1","volume-title":"Geometric Modelling for Numerically Controlled Machining","unstructured":"MARCINIAK, K. 1991. Geometric Modelling for Numerically Controlled Machining . Oxford University Press , New York . MARCINIAK, K. 1991. Geometric Modelling for Numerically Controlled Machining. Oxford University Press, New York."},{"issue":"4","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/0146-664X(82)90023-5","article-title":"A new linear algorithm for intersecting convex polygons","volume":"19","author":"O~ OURKE","year":"1982","unstructured":"O~ OURKE , J. , CHIEN, C., OLSON, T., AND NADOOR, D. 1982 . A new linear algorithm for intersecting convex polygons . Comput. Graph. Image Process. 19 , 4 , 384 - 391 . O~OURKE, J., CHIEN, C., OLSON, T., AND NADOOR, D. 1982. A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process. 19, 4, 384-391.","journal-title":"Comput. Graph. Image Process."},{"key":"e_1_2_1_22_1","volume-title":"Computational Geometry' An Introduction","author":"It AMOS","unstructured":"PREP^RATA, F. P., AND S It AMOS , M. I. 1985. Computational Geometry' An Introduction . Springer-Verlag , New York . PREP^RATA, F. P., AND SItAMOS, M. I. 1985. Computational Geometry' An Introduction. Springer-Verlag, New York."},{"key":"e_1_2_1_23_1","volume-title":"Euclidean and Non-Euclidean Geometry: An Analytic Approach","author":"Ye P.J.","unstructured":"R Ye , P.J. 1986. Euclidean and Non-Euclidean Geometry: An Analytic Approach . Cambridge University Press , Cambridge, Mass . RYe, P.J. 1986. Euclidean and Non-Euclidean Geometry: An Analytic Approach. Cambridge University Press, Cambridge, Mass."},{"issue":"6","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1016\/0031-3203(86)90043-9","article-title":"Finding the convex hull of a simple polygon in linear time","volume":"19","year":"1986","unstructured":"SHIN, S. Y., AND WOO, T.C. 1986 . Finding the convex hull of a simple polygon in linear time . Part. Recog. 19 , 6 , 453 - 458 . SHIN, S. Y., AND WOO, T.C. 1986. Finding the convex hull of a simple polygon in linear time. Part. Recog. 19, 6, 453-458.","journal-title":"Part. Recog."},{"key":"e_1_2_1_26_1","volume-title":"Oriented Projective Geometry: A Framework for Geometric Computations","unstructured":"STOLF1, J. 1991. Oriented Projective Geometry: A Framework for Geometric Computations . Academic Press , New York . STOLF1, J. 1991. Oriented Projective Geometry: A Framework for Geometric Computations. Academic Press, New York."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(91)90029-V"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(91)90011-K"},{"key":"e_1_2_1_29_1","volume-title":"Computer Numerical Control of Machine Tools","unstructured":"THYER, G.E. 1991. Computer Numerical Control of Machine Tools . 2 nd ed. Newnes , Boston . THYER, G.E. 1991. Computer Numerical Control of Machine Tools. 2nd ed. Newnes, Boston.","edition":"2"},{"issue":"3","key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/MCG.1985.276337","article-title":"A combinatorial analysis of boundary data structure schemata","volume":"5","author":"Woo T. C.","year":"1985","unstructured":"Woo , T. C. 1985 . A combinatorial analysis of boundary data structure schemata . IEEE Comput. Graph. Appl. 5 , 3 , 19 - 27 . Woo, T. C. 1985. A combinatorial analysis of boundary data structure schemata. IEEE Comput. Graph. Appl. 5, 3, 19-27.","journal-title":"IEEE Comput. Graph. Appl."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Conference on CAD \/ CAM Technology in Mechanical Engineering","author":"Woo T.C.","year":"1982","unstructured":"Woo , T.C. 1982 . Feature extraction by volume decomposition . In Proceedings of the Conference on CAD \/ CAM Technology in Mechanical Engineering ( Cambridge, Mass.). Woo, T.C. 1982. Feature extraction by volume decomposition. In Proceedings of the Conference on CAD \/ CAM Technology in Mechanical Engineering (Cambridge, Mass.)."},{"key":"e_1_2_1_32_1","volume-title":"Computing Shape","author":"W~ K","unstructured":"WOOO W~ K , J. 1986. Computing Shape . Butterworths , Boston . WOOOW~K, J. 1986. Computing Shape. Butterworths, Boston."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/159730.159732","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:24:23Z","timestamp":1672302263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/159730.159732"}},"subtitle":["computing machinability on three-, four-, and five-axis numerically controlled machines"],"short-title":[],"issued":{"date-parts":[[1993,10]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,10]]}},"alternative-id":["10.1145\/159730.159732"],"URL":"http:\/\/dx.doi.org\/10.1145\/159730.159732","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":["Computer Graphics and Computer-Aided Design"],"published":{"date-parts":[[1993,10]]},"assertion":[{"value":"1993-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}