Deborah A. Joseph

Papers

Total Citations

H-Index

About

Deborah A. Joseph is a pioneering theoretical computer scientist whose work has fundamentally shaped our understanding of the computational complexity of geometric problems. Her research primarily focuses on the intersection of computational geometry, motion planning, and robotics, where she investigates the inherent difficulty of algorithms that manipulate physical space. Joseph’s most influential contribution is her foundational analysis of the "mover's problem," demonstrating which generalizations of this basic robotics challenge lead to computationally intractable (NP-hard) scenarios—a key insight for algorithm design in automation. She also pioneered the use of approximation schemes in computational geometry, showing how to simplify complex Euclidean graphs and polyhedra for practical applications in circuit design and robotics. Her early work on robot arm kinematics provided a polynomial-time algorithm for determining joint reachability within constrained circular regions, a direct contribution to efficient motion planning. With her most cited paper accumulating 25 citations, Joseph’s research has provided essential theoretical frameworks that continue to inform modern robotics and geometric algorithm design, establishing her as a critical figure in the formal analysis of spatial computation.