New constructions of SSPDs and their applications

Mohammad A. Abam, Sariel Har-Peled

Research output: Contribution to journalArticlepeer-review

Abstract

We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of n points in Rd. 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( log2n) that has a separator of size O(n1 -1/d).

Original languageEnglish (US)
Pages (from-to)200-214
Number of pages15
JournalComputational Geometry: Theory and Applications
Volume45
Issue number5-6
DOIs
StatePublished - Jul 2012

Keywords

  • Geometric spanners
  • Separated pair decomposition
  • Separators

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

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

Cite this