Dynamic connectivity for axis-parallel rectangles

Peyman Afshani, Timothy M. Chan

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

Abstract

In this paper we give a fully dynamic data structure to maintain the connectivity of the intersection graph of n axis-parallel rectangles. The amortized update time (insertion and deletion of rectangles) is O(n 10/11 polylog n) and the query time (deciding whether two given rectangles are connected) is O(1). It slightly improves the update time (O(n0.94)) of the previous method while drastically reducing the query time (near O(n1/3)). Our method does not use fast matrix multiplication results and supports a wider range of queries.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages16-27
Number of pages12
ISBN (Print)3540388753, 9783540388753
DOIs
StatePublished - Jan 1 2006
Externally publishedYes
Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
Duration: Sep 11 2006Sep 13 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th Annual European Symposium on Algorithms, ESA 2006
CountrySwitzerland
CityZurich
Period9/11/069/13/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Dynamic connectivity for axis-parallel rectangles'. Together they form a unique fingerprint.

  • Cite this

    Afshani, P., & Chan, T. M. (2006). Dynamic connectivity for axis-parallel rectangles. In Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings (pp. 16-27). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/11841036_5