We proposed a new criterion \textit{noise-stability}, which revised the
classical rigidity theory, for evaluation of MDS algorithms which can
truthfully represent the fidelity of global structure reconstruction; then we
proved the noise-stability of the cMDS algorithm in generic conditions, which
provides a rigorous theoretical guarantee for the precision and theoretical
bounds for Euclidean embedding and its application in fields including wireless
sensor network localization and satellite positioning.
Furthermore, we looked into previous work about minimum-cost globally rigid
spanning subgraph, and proposed an algorithm to construct a minimum-cost
noise-stable spanning graph in the Euclidean space, which enabled reliable
localization on sparse graphs of noisy distance constraints with linear numbers
of edges and sublinear costs in total edge lengths. Additionally, this
algorithm enabled us to reconstruct point clouds from pairwise distances at a
minimum of $O(n)$ time complexity, down from $O(n^3)$ for cMDS.

more |
pdf
| html
None.

arxiv_cs_LG:
Noise-Stable Rigid Graphs for Euclidean Embedding. Zishuo Zhao and Shi-Min Hu https://t.co/lAWgz14VYr

Memoirs:
Noise-Stable Rigid Graphs for Euclidean Embedding. https://t.co/w8hfuI2lSA

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

We prove that every set of $n$ red and $n$ blue points in the plane contains
a red and a blue point such that every circle through them encloses at least
$n(1-\frac{1}{\sqrt{2}}) -o(n)$ points of the set. This is a two-colored
version of a problem posed by Neumann-Lara and Urrutia. We also show that every
set $S$ of $n$ points contains two points such that either (i) every circle
passing through them encloses at least $\lfloor{\frac{n-2}{3}}\rfloor$ points
of $S$, or (ii) every circle passing through them encloses at most
$\lfloor{\frac{2n-5}{3}}\rfloor$ points of $S$. The proofs make use of
properties of higher order Voronoi diagrams, in the spirit of the work of
Edelsbrunner, Hasan, Seidel and Shen on this topic. Closely related, we also
study the number of collinear edges in higher order Voronoi diagrams and
present several constructions.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 4756

Unqiue Words: 1073

The three-dimensional linear regression problem is a problem of finding a
spacial straight line best fitting a group of points in three-dimensional
Euclidean space. This problem is considered in the present paper and a solution
to it is given in a coordinate-free form.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 158,360 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible