Computational Geometry

Foundational Shape Processing

Our core contributions to computational geometry focus on algorithms that support sampling-based motion planning. Through our work on approximate convex decomposition (ACD), we introduced practical methods to partition complex polyhedra into “almost convex” components. This enables highly efficient collision detection and geometric reasoning in high-dimensional spaces, improving how configuration spaces are represented for planners.

Advanced Sampling Strategies

Building on these geometric foundations, we developed algorithms to handle severe clutter and narrow passages. By exploiting obstacle-space hierarchies and medial-axis/surface-biased sampling, we improved the decomposition of free space into viable sampling regions. We have successfully extended these concepts beyond robotics into computer-aided design (CAD) and virtual/augmented reality (VR/AR).

Swept-Volume Approximations (SPITE)

Our most recent work focuses on SPITE (Simple Polyhedral Intersection Techniques for modified Environments). SPITE utilizes 3D swept-volume approximations to rapidly validate motion-planning roadmaps as obstacles move. This geometry-aware framework transforms static roadmaps into highly responsive dynamic structures, drastically reducing update and planning times while limiting precomputation. We are currently adapting these spatial heuristics to accelerate multi-robot coordination and task and motion planning (TAMP).