Deformable spanners and applications

Area of Science:

• Computational Geometry
• Data Structures
• Algorithms

Background:

• Geometric spanners are crucial for approximating distances in point sets.
• Existing spanners often lack efficiency in dynamic or kinetic settings.
• Maintaining proximity information under point movement is a significant challenge.

Purpose of the Study:

• To propose a novel sparse (1 + ε)-spanner with a reduced number of edges.
• To develop a spanner that is efficiently maintainable under dynamic point insertions/deletions and continuous motion.
• To provide efficient kinetic algorithms for various proximity problems using the proposed spanner.

Main Methods:

• Introduction of a new sparse (1 + ε)-spanner with O(n/ε(d)) edges.
• Development of efficient maintenance strategies for dynamic point sets.
• Adaptation for kinetic data structures and a novel blackbox displacement model.
• Application to problems like closest pair and approximate nearest neighbor search.

Main Results:

• A sparse (1 + ε)-spanner with provably efficient edge complexity.
• Demonstrated efficient maintenance under dynamic point operations.
• Successful application in developing efficient kinetic algorithms for proximity queries.
• Encoding of proximity information in deforming point clouds.

Conclusions:

• The proposed deformable spanner offers a robust and efficient solution for dynamic and kinetic proximity problems.
• This work advances the state-of-the-art in maintaining geometric information in changing point sets.
• The framework facilitates efficient solutions for fundamental computational geometry problems.