NDLI: Optimal Euclidean Spanners: Really Short, Thin, and Lanky

Content Provider	ACM Digital Library
Author	Elkin, Michael Solomon, Shay
Copyright Year	2015
Abstract	The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC'95 paper, titled “Euclidean spanners: short, thin and lanky”, Arya et al. [1995] devised a construction of Euclidean (1+ε)-spanners that achieves constant degree, diameter $\textit{O}(log$ $\textit{n}),$ weight $O(log^{2}n)$ ċ $ω(\textit{MST}),$ and has running time $\textit{O}(\textit{n}$ ċ log $\textit{n}).$ This construction applies to $\textit{n}-point$ constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time. This conjecture of Arya et al. became one of the most central open problems in the area of Euclidean spanners. Nevertheless, the only progress since 1995 towards its resolution was achieved in the lower bounds front: Any spanner with diameter $\textit{O}(log$ $\textit{n})$ must incur weight Ω(log $\textit{n})$ ċ $ω(\textit{MST}),$ and this lower bound holds regardless of the stretch or the degree of the spanner [Dinitz et al. 2008; Agarwal et al. 2005]. In this article we resolve the long-standing conjecture of Arya et al. in the affirmative. We present a spanner construction with the same stretch, degree, diameter, and running time, as in Arya et al.'s result, but with optimal weight $\textit{O}(log$ $\textit{n})$ ċ $ω(\textit{MST}).$ So our spanners are as thin and lanky as those of Arya et al., but they are $\textit{really}$ short! Moreover, our result is more general in three ways. First, we demonstrate that the conjecture holds true not only in constant-dimensional Euclidean spaces, but also in doubling metrics. Second, we provide a general trade-off between the three involved parameters, which is tight in the entire range. Third, we devise a transformation that decreases the lightness of spanners in general metrics, while keeping all their other parameters in check. Our main result is obtained as a corollary of this transformation.
Starting Page	1
Ending Page	45
Page Count	45
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2819008
Journal	Journal of the ACM (JACM)
Volume Number	62
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-11-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Doubling metrics Euclidean spaces Euclidean spanners
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal euclidean spanners: really short, thin and lanky

Optimal Euclidean spanners: really short, thin and lanky (2012)

Ultra-low-dimensional embeddings for doubling metrics

Incubators vs Zombies: Fault-Tolerant, Short, Thin and Lanky Spanners for Doubling Metrics (2012)

Optimal Euclidean spanners: really short, thin and lanky

Euclidean spanners: short, thin, and lanky

Euclidean Spanners: Short, Thin, and Lanky

Document Spanners: A Formal Approach to Information Extraction

Optimal clock synchronization

Optimal Euclidean Spanners: Really Short, Thin, and Lanky

Similar Documents

Optimal euclidean spanners: really short, thin and lanky

Optimal Euclidean spanners: really short, thin and lanky (2012)

Ultra-low-dimensional embeddings for doubling metrics

Incubators vs Zombies: Fault-Tolerant, Short, Thin and Lanky Spanners for Doubling Metrics (2012)

Optimal Euclidean spanners: really short, thin and lanky

Euclidean spanners: short, thin, and lanky

Euclidean Spanners: Short, Thin, and Lanky

Document Spanners: A Formal Approach to Information Extraction

Optimal clock synchronization

Optimal Euclidean Spanners: Really Short, Thin, and Lanky