Abstract
We study the problem of partitioning a spherical representation S of a free-form surface F in 3-D, which is to partition a 3-D sphere S into two hemispheres such that a representative normal vector for each hemisphere optimizes a given global objective function. This problem arises in important practical applications, particularly surface machining in manufacturing. We model the spherical surface partition problem as processing multiple off-line sequences of insertions/deletions of convex polygons alternated with certain point queries on the common intersection of the polygons. Our algorithm combines nontrivial data structures, geometric observations, and algorithmic techniques. It takes \(O(\min\{m^2n \log \log m + \frac{m^3 \log^2(mn) \log^2(\log m)}{\log^3 m}, m^3\log^2n+mn\})\) time, where m is the number of polygons, of size O(n) each, in one off-line sequence (generally, m ≤ n). This is a significant improvement over the previous best-known O(m 2 n 2) time algorithm. As a by-product, our algorithm can process O(n) insertions/deletions of convex polygons (of size O(n) each) and queries on their common intersections in O(n 2 loglogn) time, improving over the “standard” O(n 2 logn) time solution for off-line maintenance of O(n 2) insertions/deletions of points and queries. Our techniques may be useful in solving other problems.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avis, D.: Diameter partitioning. Discrete and Computational Geometry 1(3), 265–276 (1986)
de Berg, M., Cheong, O., van Krefeld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)
Chazelle, B., Dobkin, D.P., Shouraboura, N., Tal, A.: Strategies for polyhedral surface decomposition: An experimental study. Computational Geometry: Theory and Applications 7, 327–342 (1997)
Chazelle, B., Palios, L.: Decomposition algorithms in geometry. In: Bajaj, C. (ed.) Algebraic Geometry and its Applications, vol. 27, pp. 419–447. Springer, Heidelberg (1994)
Chen, L.-L., Chou, S.-Y., Woo, T.C.: Separating and intersecting spherical polygons: Computing machinability on three-, four-, and five-axis numerically controlled machines. ACM Transactions on Graphics 12(4), 305–326 (1993)
Chen, L.L., Woo, T.C.: Computational geometry on the sphere for automated machining. ASME J. Mech. Des. 114(2), 288–295 (1992)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
Dyer, M.E.: Linear time algorithms for two- and three-variable linear programs. SIAM Journal on Computing 13, 31–45 (1984)
Edelsbrunner, H.: Dynamic data structures for orthogonal intersection queries, Report F59, Institut für Informationsverarbeitung, Technische Universität Graz, Graz, Austria (1980)
Gupta, P., Janardan, R., Majhi, J., Woo, T.: Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC-machining. Computer-Aided Design 28(8), 577–587 (1996)
Hershberger, J., Suri, S.: Finding tailored partitions. In: Proc. 5th Annual ACM Symposium on Computational Geometry, pp. 255–265 (1989)
Hershberger, J., Suri, S.: Off-line maintenance of planar configurations. Journal of Algorithms 21, 453–475 (1996)
Katz, S., Tal, A.: Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics (SIGGRAPH 2003) 22(3), 954–961 (2003)
Megiddo, N.: Linear programming in linear time when the dimension is fixed. Journal of ACM 31, 114–127 (1984)
Megiddo, N., Supowit, K.: On the complexity of some common geometric location problems. SIAM Journal on Computing 13(1), 182–196 (1984)
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888–905 (2000)
Sonka, M., Hlavac, V., Boyle, R.: Image Processing, Analysis, and Machine Vision, 2nd edn. PWS Pub. (1999)
Tang, K., Liu, Y.-J.: An optimization algorithm for free-form surface partitioning based on weighted Gaussian image. Graphical Models 67, 17–42 (2005)
Tang, K., Woo, T., Gan, J.: Maximum intersection of spherical polygons and workpiece orientation for 4- and 5-axis machining. Journal of Mechanical Design 114, 477–485 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, D.Z., Misiołek, E. (2008). Free-Form Surface Partition in 3-D. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_47
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)