Reproduce “A Sublinear Algorithm for Path Feasibility Among Rectangular Obstacles” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Alex Fan, Alicia Li, Arul Kolla, Jason Gonzalez
MIT researchers developed a sublinear-time algorithm for determining path feasibility for rectangular robots navigating among potentially overlapping rectangular obstacles. The method utilizes a generalized Gabriel graph framework under the L0 norm, achieving O(n log n) preprocessing time and O(log n) query time for path existence.
Key insights
- The continuous path feasibility problem can be decomposed into pairwise passability constraints between obstacles and region constraints.
- A generalized Gabriel graph framework under the L0 norm can effectively capture spatial relationships and minimum gap widths between rectangular obstacles, even when they overlap.
- Persistent Disjoint-Set Union (DSU) on the dual of this graph allows efficient querying of connectivity for varying robot dimensions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.