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

DOI10.1007/S10107-016-1058-7zbMATH Open1372.65057arXiv1503.07901OpenAlexW2265336713MaRDI QIDQ526832FDOQ526832

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)

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.

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Robust Hausdorff distance matching algorithms using pyramidal structures
• Using jointly geometry and algebra to determine RC-constructibility

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)