A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES

DOI10.15807/JORSJ.35.353MaRDI QIDQ5288735zbMATH OpenOpenAlexFDO

Authors Satoru Fujishige, Ping Zhan

Publication date 17 August 1993

Published in Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL https://doi.org/10.15807/jorsj.35.353

zbMATH Keywords

polytopesnearest pair of pointsseparating-hyperplane algorithm

Mathematics Subject Classification ID

Nonlinear programming (90C30) Nonsmooth analysis (49J52) Computational methods for problems pertaining to operations research and mathematical programming (90-08) (n)-dimensional polytopes (52B11) Continuous location (90B85)

Recommendations

• An iterative algorithm for finding a nearest pair of points in two convex subsets of \(\mathbb{R}^n\)
• A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
• A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes
• Finding a best approximation pair of points for two polyhedra
• Dual vectors and lower bounds for the nearest lattice point problem
• The nearest point problem in a polyhedral set and its extensions
• scientific article; zbMATH DE number 730000
• An algorithm for solving the nearest point problem in an affine subspace
• On the complexity of closest pair via polar-pair of point-sets
• On the complexity of closest pair via polar-pair of point-sets

Cited in

(17)

• A note concerning the closest point pair algorithm.
• Zonotopes and the LP-Newton method
• The nearest point problem in a polyhedral set and its extensions
• A practical approach to the 2D incremental nearest-point problem suitable for different point distributions
• Two-dimensional closest pair problem: a closer look
• An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane
• A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes
• An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
• A simple projection algorithm for linear programming problems
• Efficient computation of dual space and directional multiplicity of an isolated point
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• scientific article; zbMATH DE number 730000 (Why is no real title available?)
• An iterative algorithm for finding a nearest pair of points in two convex subsets of \(\mathbb{R}^n\)
• Clipping algorithms for solving the nearest point problem over reduced convex hulls
• Algorithms and Computation
• A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
• Finding a best approximation pair of points for two polyhedra

This page was built for publication: A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES

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