Drone Room Detection

This project was supervised by Prof. Dan Feldman. ORB-SLAM is a monocular SLAM library that can output (among other things) 3D collision datapoints from a single-camera drone setup.

Given these 3-dimensional points, one challenge is to identify the room that the drone is in (assuming that it is navigating inside a building). In this project we devised an optimal algorithm for identifying the walls of the room, that can run in linear time with respect to the number of datapoints.
Keywords:

• Optimality Prooving
• Linear Time
• SMAWK

Linear time improvement is achieved using SMAWK algorithm, which has also found use in Bioinformatics.
SMAWK requires an implicitly-defined totally monotone matrix, which is explicitly defined in the following algorithm, making its implementation trivial.

Link to the PDF:

Optimal Algorithm.pdf Project Report.pdf