Group Abstract Group Abstract

Message Boards Message Boards

0
|
3.6K Views
|
7 Replies
|
1 Total Like
View groups...
Share
Share this post:

TSP Geometry conjecture

Posted 10 years ago
POSTED BY: Brian Davis
7 Replies
Posted 10 years ago
POSTED BY: Brian Davis

As best I can tell you want to take a matrix of valid planar distances and recover a set of points whose pairwise distances recover that matrix. This can be done using singular value decomposition. Details and Mathematica/WL code may be found in this recent TMJ article.

POSTED BY: Daniel Lichtblau
Posted 10 years ago

Wonderful and relevant article thank you very much for this! MDS is an existing method for converting the data I described into 2D points. It seems they have some margin of error, and i wonder how a circle intersect solution (something like what i proposed in the original post) would compare on accuracy and performance.

Anyway, it looks like MDS is built into Mathematica/WL already, that is terrific!

POSTED BY: Brian Davis

In this instance I think it is the PCA approach that would be of greater use. Assuming the distances came from actual points in a plane, one can use PCA to recover the relative placement of the points, that is, it will be correct up to translation and rotation/reflection.

POSTED BY: Daniel Lichtblau
Posted 10 years ago

PCA is a fairly common acronym so I would like to mention this link in the discussion to provide reference to PCA in this context: https://en.wikipedia.org/wiki/Principalcomponentanalysis

also a helpful quote from that link:

"Mathematica – Implements principal component analysis with the PrincipalComponents command using both covariance and correlation methods."

@Daniel Lichtblau: "it will be correct [with the exception of] translation and rotation/reflection." That is exactly what I am looking for, thank you again. Also thanks for this clarification about the accuracy of PCA, it was difficult to discern that fact from the article I read.

POSTED BY: Brian Davis

Dear @Brian Davis what relation does your question have to Wolfram Technologies?

This forum permits only subjects related to Wolfram Technologies. Post elsewhere for other subjects or make clear the connection to Wolfram Technologies. Please read the guidelines.

POSTED BY: EDITORIAL BOARD
Posted 10 years ago

Thank you, I have updated my post to be more compliant.

POSTED BY: Brian Davis
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard