Kinetic spanners in Rd

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Mohammad Abam, Denmark
  • Mark de Berg, Tue, Netherlands
  • Department of Computer Science
We present a new (1+ε)-spanner for sets of n points in Rd. Our spanner has size O(n/εd-1) and maximum degree O(logd n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n2d-1), and using a supporting data structure of size O(n logdn) we can handle events in time O(logd+1n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in Rd whose performance does not depend on the spread of the point set.
Original languageEnglish
Title of host publicationAnnual Symposium on Computational Geometry : SESSION: Monday, June 8th, 10:50-11:50 am
EditorsJohn Hershberger, Efi Fogel
Number of pages8
PublisherAssociation for Computing Machinery
Publication year2009
ISBN (print)978-1-60558-501-7
Publication statusPublished - 2009
EventACM Symposium On Computational Geometry (SCG) - Aarhus, Denmark
Duration: 8 Jun 200910 Jun 2009
Conference number: 25


ConferenceACM Symposium On Computational Geometry (SCG)

    Research areas

  • geometric spanners, kinetic data structures

See relations at Aarhus University Citationformats

ID: 17919873