×
Wallner, Johannes; Schröcker, Hans-Peter; Hu, Shi-Min

Tolerances in geometric constraint problems. (English) Zbl 1075.65025

Reliab. Comput. 11, No. 3, 235-251 (2005).
Geometric constraint solving is a term of computer-aided design and means the problems which arise when the location of geometric objets is described via geometric relations between them. The issues crucial for engineering applications are solvability of constraint problems and the sensitivity to errors.
The authors deal with the propagation of errors through implicit constraints. Based on the concept of tolerance zone, they show how to handle error propagation in the form of tolerance zones through implicit constraints in a way independent of solvability. The usage of tolerance zones generalizes interval arithmetic in the sense that intervals are tolerance zones of real numbers.
More precisely, authors assume that a certain number of geometric objects is given imprecisely, each of them is only known to be contained in a certain tolerance zone. Other geometric objects are located via constraints, and one wants to give tolerance zones for them. This is done by linearizing the system of constraints and giving upper bounds for the linearization error. Depending on the problem, there is a maximum size of tolerance zone for which this method is applicable. Computing this radius of validity and the linearization error requires upper bounds on the constraints’ second derivatives in the form of bilinear mappings. It turns out that such bounds are found easily of the constraints are quadratic, which is very often the case for geometric constraints.
Reviewer: Sonia Pérez Díaz (Madrid)

Cited in 2 Documents

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)

Keywords:

geometric constraints; tolerance zone; linearization error; computer-aided design; error propagation; interval arithmetic; geometric objects

Software:

mctoolbox
PDF BibTeX XML Cite
\textit{J. Wallner} et al., Reliab. Comput. 11, No. 3, 235--251 (2005; Zbl 1075.65025)
Full Text: DOI Link
  • logo of hbz
  • logo of WorldCat

References:

[1] Asimov, L. and Roth, B.: The Rigidity of Graphs, Trans. Amer. Math. Soc. 245 (1978), pp. 171–190.
[2] Asimov, L. and Roth, B.: The Rigidity of Graphs II, J. Math. Anal. Appl. 68 (1979), pp. 171–190. · Zbl 0441.05046
[3] Bhatia, R.: Matrix Analysis, Springer, 1997. · Zbl 0863.15001
[4] Bouma, W., Fudos, I., Hoffmann, C., Cai, J., and Paige, R.: Geometric Constraint Solver, Computer-Aided Design 27 (1995), pp. 487–501. · Zbl 0960.68721
[5] Bruederlin, B.: Using Geometric Rewriting Rules for Solving Geometric Problems Symbolically, Theoret. Comput. Sci. 116 (1993), pp. 291–303. · Zbl 0795.68175
[6] Cauchy, A. L.: IIe mémoire sur les polygones et les polyèdres, Journal de l’Ecole Polytechnique 19 (1813), pp. 87–98.
[7] Conelly, R.: On Generic Global Rigidity, in: Gritzmann, P. and Sturmfels, B.(eds), Applied Geometry and Discrete Mathematics–The Victor Klee Festschrift, American Mathematical Society,
[8] Crippen, G. M. and Havel, T. F.: Distance Geometry and Molecular Conformation, Chemometrics Series 15, Research Studies Press Ltd., Chichester, 1988. · Zbl 1066.51500
[9] Fudos, I. and Hoffmann, C.: A Graph-Constructive Approach to Solving Systems of Geometric Constraints, ACMTransactions on Graphics 16 (1997), pp. 179–216.
[10] Gao, X. S. and Chou, S. C.: Solving Geometric Constraint Systems. I.A Global Propagation Approach, Computer-Aided Design 30 (1998), pp. 47–54. · Zbl 05470939
[11] Gao, X. S. and Chou, S. C.: Solving Geometric Constraint Systems. II.A Symbolic Approach and Decision of rc-Constructibility, Computer-Aided Design 30 (1998), pp. 115–122. · Zbl 05470929
[12] Ghosh, P.: A Unified Computational Framework for Minkowski Operations, Computers & Graphics 17 (1993), pp. 357–378.
[13] Higham, N. J.: Accuracy and Stability of Numerical Algorithms, Soc. Industrial and Appl. Math, 1996, Section 6.2. · Zbl 0847.65010
[14] Hoffmann, C. M.: Robustness in Geometric Computations, Journal of Computing and InformationScience in Engineering 1 (2001), pp. 143–156.
[15] Hoffmann, C. M. and Vermeer, P.: Geometric Constraint Solving in R2 and R3, in: Du, D.-Z. and Hwang, F. K.(eds.), Computing in Euclidean Geometry, World Scientific, 1995, pp. 266–298.
[16] Hu, S.-M. and Wallner, J.: ErrorPropagation through Geometric Transformations, Technical Report 102, Institut four Geometrie, TU Wien, 2003.
[17] Kondo, K.: Algebraic Method for Manipulation of Dimensional Relationships in Geometric Models, Computer-Aided Design 24 (1992), pp. 141–147. · Zbl 0752.65106
[18] Laman, G.: On Graphs and Rigidity of Plane Skeletal Structures, J. Engrg. Math. 4 (1970), pp. 331–340. · Zbl 0213.51903
[19] Lamure, H. and Michelucci, D.: Solving Geometric Constraints by Homotopy, IEEE Trans. Vis. Comp. Graph. 2 (1996), pp. 28–34. · Zbl 05108141
[20] Lee, J. Y. and Kim, K.: A 2-D Geometric Constraint Solver Using DOF-Based Graph Reduction, Computer-Aided Design 30 (1998), pp. 883–896. · Zbl 1069.68630
[21] Lee, K.-Y., Kwon, O.-H., Lee, J.-Y., and Kim, T. W.: A Hybrid Approach to Geometric Constraint Solving with Graph Analysis and Reduction, Adv. Eng. Software 34 (2003), pp. 103–113. · Zbl 01963201
[22] Li, Y.-T., Hu, S.-M., and Sun, J.-G.: A Constructive Approach to Solving 3-D Geometric Constraint Systems Using Dependence Analysis, Computer-Aided Design 34 (2002), pp. 97–108 · Zbl 05860876
[23] Light, R. A. and Gossard, D. C.: Modification of Geometric Models through Variational Geometry, Computer-Aided Design 14 (1982), pp. 209–214.
[24] Pottmann, H., Odehnal, B., Peternell, M., Wallner, J., and Haddou, R. A.: On Optimal Tolerancing in Computer-Aided Design, in: Martin, R. and Wang, W.(eds), Geometric Modeling and Processing 2000, IEEE Computer Society, Los Alamitos, 2000, pp. 347–363.
[25] Pottmann, H. and Wallner, J.: Computational Line Geometry, Springer, 2001. · Zbl 1006.51015
[26] Requicha, A. A. G.: Towards a Theory of Geometric Tolerancing, Internat. J. Robotics Res. 2 (1983), pp. 45–60.
[27] Servatius, B. and Whiteley, W.: Constraining Plane Configurations in Computer-Aided Design: Combinatorics of Directions and Lengths, SIAM J. Discret. Math. 12 (1999), pp. 136–153. · Zbl 0916.68182
[28] Stachel, H.: Higher-Order Flexibility for a Bipartite Planar Framework, in: Kecskeméthy, A., Schneider, M., and Woernle, C.(eds) Advances in Multi-Body Systems and Mechatronics, Inst. f. Mechanik und Getriebelehre der TU Graz, Duisburg, 1999, pp. 345–357.
[29] Verroust, A., Schonek, F., and Roller, D.: Rule-Oriented Method for Parametrized ComputerAided Design, Computer-Aided Design 25 (1993), pp. 531–540. · Zbl 0760.65017
[30] Wallner, J., Krasauskas, R., and Pottmann, H.: Error Propagation in Geometric Constructions, Computer-Aided Design 32 (2000), pp. 631–641. · Zbl 05860768
[31] Whitely, W.: Infinitesimal Motions of a Bipartite Framework, Pacific J. Math. 110 (1984), pp. 233–255. · Zbl 0476.70003
[32] Wunderlich, W.: Ebene Kinematik, BI-Hochschultaschenb ücher 447/447a, Bibliograph. Inst., Mannheim, 1970. · Zbl 0225.70002
[33] Wunderlich, W.: Über Ausnahmefachwerke, deren Knoten auf einem Kegelschnitt liegen, Acta Math. 47 (1983), pp. 291–300. · Zbl 0534.51022
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.