New constructions of SSPDs and their applications

Mohammad Ali Abam, Sariel Har-Peled

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a new optimal construction of semi-separated pair decomposition (SSPD) for a set of n points in ℝd. In the new construction each point participates in a few pairs, and it extends easily to spaces with low doubling dimension. This is the first optimal construction with these properties. As an application of the new construction, for a fixed t > 1, we present a new construction of a t-spanner with O(n) edges and maximum degree O(log2 n) that has a separator of size O (n1-1/d).

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
Pages192-200
Number of pages9
DOIs
StatePublished - Jul 30 2010
Event26th Annual Symposium on Computational Geometry, SoCG 2010 - Snowbird, UT, United States
Duration: Jun 13 2010Jun 16 2010

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other26th Annual Symposium on Computational Geometry, SoCG 2010
CountryUnited States
CitySnowbird, UT
Period6/13/106/16/10

Keywords

  • Geometric spanners
  • Separated pair decomposition
  • Separators

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'New constructions of SSPDs and their applications'. Together they form a unique fingerprint.

Cite this