A robust and efficient method for solving point distance problems by homotopy. (English) Zbl 1372.65057
Summary: The goal of Point Distance Solving Problems is to find 2D or 3D placements of points knowing distances between some pairs of points. The common guideline is to solve them by a numerical iterative method (e.g. Newton-Raphson method). A sole solution is obtained whereas many exist. However the number of solutions can be exponential and methods should provide solutions close to a sketch drawn by the user. Geometric reasoning can help to simplify the underlying system of equations by changing a few equations and triangularizing it. This triangularization is a geometric construction of solutions, called construction plan. We aim at finding several solutions close to the sketch on a one-dimensional path defined by a global parameter-homotopy using a construction plan. Some numerical instabilities may be encountered due to specific geometric configurations. We address this problem by changing on-the-fly the construction plan. Numerical results show that this hybrid method is efficient and robust.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
Keywords:
point distance solving problems; reparameterization; curve tracking; symbolic-numeric algorithmSoftware:
HOM4PSReferences:
| [1] | Allgower, E., Georg, K.: Numerical path following. Handb. Numer. Anal. 5(3), 207 (1997) |
| [2] | Barki, H., Fang, L., Michelucci, D., Foufou, S.: Re-parameterization reduces irreducible geometric constraint systems. Comput. Aided Des. 70, 182-192 (2016) · doi:10.1016/j.cad.2015.07.011 |
| [3] | Durand, C., Hoffmann, C.: A systematic framework for solving geometric constraints analytically. J. Symb. Comput. 30(5), 493-519 (2000) · Zbl 0967.65029 · doi:10.1006/jsco.2000.0392 |
| [4] | Fabre, A., Schreck, P.: Combining symbolic and numerical solvers to simplify indecomposable systems solving. In: Proceedings of ACM Symposium on Applied Computing SAC, 2008, pp. 1838-1842. ACM, New York (2008) |
| [5] | Faudot, D., Michelucci, D.: A new robust algorithm to trace curves. Reliab. Comput. 13(4), 309-324 (2007) · Zbl 1120.65016 · doi:10.1007/s11155-007-9036-7 |
| [6] | Foufou, S., Michelucci, D.: The Bernstein basis and its applications in solving geometric constraint systems. Reliab. Comput. 17(2), 192-208 (2012) · Zbl 1247.68309 |
| [7] | Gao, X.S., Hoffmann, C.M., Yang, W.Q.: Solving spatial basic geometric constraint configurations with locus intersection. In: Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications. SMA ’02, pp. 95-104. ACM, New York (2002) |
| [8] | Imbach, R., Mathis, P., Schreck, P.: Tracking method for reparametrized geometrical constraint systems. In: 2011 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 31-38. IEEE (2011) |
| [9] | Imbach, R., Schreck, P., Mathis, P.: Leading a continuation method by geometry for solving geometric constraints. Comput. Aided Des. 46, 138-147 (2014) · doi:10.1016/j.cad.2013.08.026 |
| [10] | Kearfott, R., Xing, Z.: An interval step control for continuation methods. SIAM J. Numer. Anal. 31(3), 892-914 (1994) · Zbl 0809.65050 · doi:10.1137/0731048 |
| [11] | Lamure, H., Michelucci, D.: Solving geometric constraints by homotopy. In: Proceedings of the Third ACM Symposium on Solid Modeling and Applications. SMA ’95, pp. 263-269. ACM, New York (1995) |
| [12] | Lee, T.L., Li, T.Y., Tsai, C.H.: Hom4ps-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method. Computing 83, 109-133 (2008) · Zbl 1167.65366 · doi:10.1007/s00607-008-0015-6 |
| [13] | Li, T., Wang, X.S.: Solving real polynomial systems with real homotopies. Math. Comput. 60(202), 669-680 (1993) · Zbl 0779.65033 · doi:10.1090/S0025-5718-1993-1160275-5 |
| [14] | Lovász, L., Plummer, MD.: Matching Theory, vol. 367. American Mathematical Society, Providence (2009) · Zbl 1175.05002 |
| [15] | Martin, B., Goldsztejn, A., Granvilliers, L., Jermann, C.: Certified parallelotope continuation for one-manifolds. SIAM J. Numer. Anal. 51(6), 3373-3401 (2013) · Zbl 1298.65088 · doi:10.1137/130906544 |
| [16] | Mathis, P., Schreck, P., Imbach, R.: Decomposition of geometrical constraint systems with reparameterization. In: Ossowski, S., Lecca, P. (eds.) SAC, pp. 102-108. ACM (2012) |
| [17] | Mourrain, B., Pavone, J.P.: Subdivision methods for solving polynomial equations. J. Symb. Comput. 44(3), 292-306 (2009) · Zbl 1158.13010 · doi:10.1016/j.jsc.2008.04.016 |
| [18] | Porta, J.M., Ros, L., Thomas, F., Corcho, F., Cantó, J., Pérez, J.J.: Complete maps of molecular-loop conformational spaces. J. Comput. Chem. 28(13), 2170-2189 (2007) · doi:10.1002/jcc.20733 |
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.
