### Top 3 Arxiv Papers Today in Computational Geometry

##### #1. Noise-Stable Rigid Graphs for Euclidean Embedding
###### Zishuo Zhao, Shi-Min Hu
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.
###### Tweets
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.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #2. On circles enclosing many points
###### Mercè Claverol, Clemens Huemer, Alejandra Martínez-Moraian
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.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 4756
Unqiue Words: 1073

##### #3. On linear regression in three-dimensional Euclidean space
###### O. V. Ageev, R. A. Sharipov
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.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

###### About

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.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 158,360 papers.