Micha Sharir, Professor Emeritus of Computer Science at Tel Aviv University, has won the 2025 Donald E. Knuth Prize for seminal contributions to computational and discrete geometry, the development of algorithmic motion planning, transforming the field of computational geometry, and inspiring generations of researchers.
Over four decades, Sharir has profoundly shaped the theoretical foundations of geometric algorithms, bridging computer science and mathematics in transformative ways.
Sharir's early research with Jacob T. Schwartz on the piano movers' problem laid the groundwork for algorithmic motion planning, a field that he helped define and integrate into the theoretical computer science canon. His introduction of algebraic tools such as cylindrical algebraic decomposition brought methods from real algebraic geometry into algorithm design, influencing areas ranging from robotics to symbolic computation.
In his work on arrangements, lower envelopes, and Davenport-Schinzel sequences, he championed an approach to computational geometry in which algorithmic complexity followed from combinatorial complexity, and provided a unifying framework for a wide range of problems in geometric optimization and the construction of geometric data structures. His co-authored randomized subexponential algorithm for linear programming and for so-called LP-type problems, a notion that he introduced with Emo Welzl, is based on combinatorial and geometric insights and remains a cornerstone of geometric optimization.
Sharir has had a lasting and central role in incidence geometry, where he developed deep results over several decades, including the influential Elekes-Sharir framework connecting point-line incidences to classical problems such as distinct distances. These ideas laid the groundwork for the breakthrough Guth-Katz bound on distinct distances in the plane and inspired a long line of further results—by Sharir and his students and by others. His work in this area blends combinatorics, algebraic geometry, and algorithm design, and continues to shape the modern theory of discrete geometry.
In recent years, Sharir has contributed significantly to the algorithmic application of polynomial partitioning for range searching with semi-algebraic sets. Building on influential work by Matoušek and Patáková and by Agarwal, Aronov, Ezra, and Zahl (three of whom are his former students), Sharir and collaborators have obtained improved data structures and query bounds for high-dimensional geometric search problems. This line of work has resolved long standing open problems and broadened the scope of algebraic tools in computational geometry.
Sharir is also renowned for his deep engagement with the research community. He has mentored 27 PhD students and built a large and vibrant academic lineage. His collaborations span over 250 researchers worldwide, and his influential monograph, Davenport-Schinzel Sequences and Their Geometric Applications, continues to educate and inspire new generations of theorists.
Prize Committee:
Noga Alon (Princeton)
Edith Cohen (Chair, Google/Tel Aviv U.)
David Eppstein (UC Irvine)
Valerie King (U. of Victoria)
Salil Vadhan (Harvard U.)
Moshe Vardi (Rice U.)