A robust and efficient method for solving point distance problems by homotopy

DOI10.1007/S10107-016-1058-7MaRDI QIDQ526832zbMATH OpenOpenAlexFDO

Authors Rémi Imbach, Pascal Mathis, Pascal Schreck

Publication date 15 May 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.07901

zbMATH Keywords

reparameterizationsymbolic-numeric algorithmcurve trackingpoint distance solving problems

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)

Abstract: 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 (emph{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.

Recommendations

• A \(k\)-points-based distance for robust geometric inference
• New methods for the distance geometry problem
• A simplicial homotopy algorithm for computing zero points on polytopes
• Efficient computation of the Hausdorff distance between polytopes by exterior random covering
• scientific article; zbMATH DE number 1424308
• Affine invariant comparison of point-sets using convex hulls and Hausdorff distances
• An implementation of the piecewise-linear homotopy algorithm for the computation of fixed points
• Efficient geodesics and an effective algorithm for distance in the complex of curves
• Approximating loops in a shortest homology basis from point data

Cites work

• A new robust algorithm to trace curves
• A systematic framework for solving geometric constraints analytically
• An Interval Step Control for Continuation Methods
• Certified parallelotope continuation for one-manifolds
• HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method
• Interrogating witnesses for geometric constraint solving
• Matching theory
• Solving Real Polynomial Systems with Real Homotopies
• Subdivision methods for solving polynomial equations

Cited in

(4)

• scientific article; zbMATH DE number 175988 (Why is no real title available?)
• scientific article; zbMATH DE number 7760161 (Why is no real title available?)
• Robust Hausdorff distance matching algorithms using pyramidal structures
• Using jointly geometry and algebra to determine RC-constructibility

Describes a project that uses

Uses Software

• HOM4PS

This page was built for publication: A robust and efficient method for solving point distance problems by homotopy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526832)