Dan Halperin

Research

Current Interests: computational geometry and its applications, robust geometric computing and CGAL, robotics and automation, algorithmic motion planning, 3D printing
List of publications: dblp
More details about my lab’s work can be found by clicking on the relevant tabs at the top of the page; for a quick overview visit the CGL projects page

Excerpts

Chapters in the 3rd Edition of the Handbook of Discrete and Computational Geometry (Goodman, O’Rourke, Toth, Editors):
28. Arrangements (with Micha Sharir), 50. Algorithmic Motion Planning (with Oren Salzman and Micha Sharir), and 51. Robotics (with Lydia Kavraki and Kiril Solovey)
From Piano Movers to Piano Printers: Computing and Using Minkowski Sums, keynote talk at WAFR 2016
Hard versus Easy in Robot Motion Planning: Closing the Ring (YouTube), keynote talk at ICRA 2015, EuroCG 2016
On the Hardness of Unlabeled Multi-Robot Motion Planning, best student paper award to Kiril Solovey at RSS 2015

Teaching

Courses

Research

Excerpts

Teaching

Selected Projects

Advantages of Using Two Robotic Arms for Tight Assemblies

Indoor Localization of UAVs Using Only Few Measurements by Output-Sensitive Preimage Intersection

A Full-Cycle Assembly Operation: From Digital Planning to Trajectory Execution Using a Robotic Arm

Sensor Localization by Few Distance Measurements via the Intersection of Implicit Manifolds

A First Demonstration of a Robotic Arm Solving the Alpha Puzzle

Tight Motion Planning by Riemannian Optimization for Sliding and Rolling with Finite Number of Contact Points

Localization with Few Distance Measurements

Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity

Refined Hardness of Distance-Optimal Multi-Agent Path Finding

CGAL Python Bindings

Near-Optimal Multi-Robot Motion Planning with Finite Sampling

Collision Detection Between Neurons and Blood Vessels

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

Optimized Synthesis of Snapping Fixtures

Space-Aware Reconfiguration

Robust 2D Assembly Sequencing via Geometric Planning with Learned Scores

Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead

Throwing a Sofa Through the Window

Scalable Asymptotically-Optimal Multi-Robot Motion Planning

Sampling-Based Bottleneck Pathfinding With Applications To Fréchet Matching

Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning With Forward Propagation

Motion Planning for Multiple Unit-Ball Robots in \(\mathbb{R}^d\)

Optimal Area Polygonalization

On the Separation of a Polyhedron from Its Single-Part Mold

The Offset Filtration of Convex Objects

Motion Planning for Multi-Link Robots by Implicit Configuration-Space Tiling

Motion Planning for Unlabeled Discs with Optimality Guarantees

Exact Minkoski Sums of Polygons With Holes

Effective Metrics for Multi-Robot Motion-Planning

Efficient high-quality motion planning by fast all-pairs \(r\)-nearest-neighbors

PSPACE-hardness of unlabeled motion planning and variants

Asymptotically-Optimal Motion Planning using Lower Bounds on Cost

Asymptotically near-optimal RRT for fast, high-quality, motion planning

Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons

Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-Robot Motion Planning

Sparsification of Motion-Planning Roadmaps by Edge Contraction

Planar Point Location – Depth vs. Max Query Length

\(k\)-Color Multi-Robot Motion Planning

Motion Planning via Manifold Samples

Sampling-Diagrams Automata: a Tool for Analyzing Path Quality in Tree Planners

Efficient retrieval of Minkowski sum of rotating polytopes

Exact Voronoi Diagram of Arbitrary Lines in Space

Deconstructing Approximate Offsets

Constructing Approximate Offsets

Lines Through Segments

Improving Path Quality by a Path Merging Algorithm

Snap Rounding on the Sphere

Efficient Construction of Pathways in the Complement of the Union of Balls in R3

Polyhedral Assembly Partitioning with Infinite Translations

PathRover—Rapid Sampling and Optimization of Molecular Motions

Arrangements of Geodesic Arcs on the Sphere

A general framework for processing a set of curves defined on a continuous two-dimensional parametric surface

Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes

Exact and Efficient Construction of Planar Minkowski Sums using the Convolution Method

Exact and Approximate Construction of Offset Polygons

Planning Near Optimal Corridors

The Complexity of the Outer Face in Arrangements of Random Segments

On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra

Landmarks Point Location

Dynamic Maintenance of Molecular Surfaces under Conformational Changes

Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra with Applications

The Visibility-Voronoi Complex

Path Verification for NC-Machining

Controlled Perturbation for Arrangements of Circles

Controlled Perturbation of Polyhedral Surfaces

Controlled Perturbation of Spherical Arrangements

Lower Envelopes of Planar Curves

Adaptive Point Location of Parametric Curves

Window Cleaning Swarm Apparatus

Mini Supertanker

2D Part Orienting

Eroding 3D Parts

Converting GCode to STL

Path Following using Drones

Motion Planning for Physical Robots Among Dynamic Obstacles

A Full-Cycle Assembly Operation:
From Digital Planning to Trajectory Execution Using a Robotic Arm

Tight Motion Planning by Riemannian Optimization
for Sliding and Rolling with Finite Number of Contact Points