×

Sets of lines and cutting out polyhedral objects. (English) Zbl 1022.65022

The authors study algorithmic problems related to manufacturing applications of hot wire cutters. Such cutters are popular manufacturing tools for cutting expanding polystyrene (styrofoam) with a thin moving heated wire. In particular the question of polyhedral-wise continuity is studied: Can a given object be cut out without disconnecting and then reataching the wire?
In an abstract setting this question translates to properties of sets of lines and segments and therefore becomes suitable for computational geometry techniques. On the combinatorial and algorithmic levels the results and methods are related to two problems:
(1) Given a set \(F= \{f_1, f_2,\dots, f_k\}\) of polygons and a polygon \(f\) decide if there is a subset of lines in the set of lines not stability \(F\) that cover \(f\).
(2) Construct the connectivity graph for free movements of lines that maintain contact with the polyhedral shape.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chazelle, B.; Edelsbrunner, H.; Guibas, L. J.; Sharir, M., Algorithms for bichromatic line segment problems and polyhedral terrains, Algorithmica, 11, 116-132 (1994) · Zbl 0818.68140
[2] Coxeter, H. S.M., Projective Geometry (1974), University of Toronto: University of Toronto Toronto · Zbl 0272.50015
[3] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer-Verlag: Springer-Verlag Berlin · Zbl 0634.52001
[4] Edelsbrunner, H.; Maurer, H. A.; Preparata, F. P.; Rosenberg, A. L.; Welzl, E.; Wood, D., Stabbing line segments, BIT, 22, 274-281 (1982) · Zbl 0484.68053
[5] J.W. Jaromczyk, M. Kowaluk, Generalized skewed projections in \(R^3\); J.W. Jaromczyk, M. Kowaluk, Generalized skewed projections in \(R^3\) · Zbl 0757.05062
[6] Jaromczyk, J. W.; Kowaluk, M., Skewed projections with an application to line stabbing in \(R^3\), (Proc. 4th Annu. ACM Sympos. Comput. Geom., New York (1988), ACM Press), 362-370
[7] Jaromczyk, J. W.; Kowaluk, M., The face-wise continuity in hot wire cutting of polyhedral objects, (Proc. 16th European Workshop on Computational Geometry, Eilat (2000)), 93-97
[8] Jaromczyk, J. W.; Kowaluk, M., Set of lines and cutting out polyhedral objects, (Proc. 17th European Workshop on Computational Geometry, Berlin (2001)), 183-186
[9] Lozano-Pérez, T., Spatial planning: A configuration space approach, IEEE Trans. Comput., C-32, 108-120 (1983) · Zbl 0513.68081
[10] Overmars, M.; de Berg, M.; van Kreveld, M.; Schwarzkopf, O., Computational Geometry: Algorithms and Applications (1999), Springer-Verlag: Springer-Verlag Berlin
[11] McKenna, M.; O’Rourke, J., Arrangements of lines in 3-space: A data structure with applications, (Proc. 4th Annu. ACM Sympos. Comput. Geom., New York (1988), ACM Press), 371-380
[12] Nurmi, O.; Sack, J.-R., Separating a polyhedron by one translation from a set of obstacles, (Proc. 14th Internat. Workshop Graph-Theoret. Concepts Comput. Sci.. Proc. 14th Internat. Workshop Graph-Theoret. Concepts Comput. Sci., Lecture Notes Comput. Sci., 344 (1989), Springer-Verlag: Springer-Verlag Berlin), 202-212
[13] Nussbaum, D.; Sack, J.-R., Translation separability of polyhedra, (Abstracts 1st Canad. Conf. Comput. Geom. (1989)), 34
[14] Pellegrini, M., Lower bounds on stabbing lines in 3-space, Computational Geometry, 3, 53-58 (1993) · Zbl 0771.68107
[15] Pellegrini, M., Ray shooting and lines in space, (Goodman, Jacob E.; O’Rourke, Joseph, Handbook of Discrete and Computational Geometry (1997), CRC Press LLC: CRC Press LLC Boca Raton, FL), 599-614, Chapter 32 · Zbl 0907.68198
[16] Schwartz, J. T.; Sharir, M., On the piano mover’s problem: V. the case of a rod moving in three-dimensional space amidst polyhedral obstacles, (Sharir, M.; Schwartz, J. T.; Hopcroft, J., Planning, Geometry, and Complexity of Robot Motion (1986), Ablex Publishing Corporation: Ablex Publishing Corporation Norwood, NJ), 154-186
[17] Schwartz, J. T.; Sharir, Micha, A survey of motion planning and related geometric algorithms, (Kapur, D.; Mundy, J., Geometric Reasoning (1989), MIT Press: MIT Press Cambridge, MA), 157-169 · Zbl 0676.68086
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.