Joseph S.B. Mitchell

About

Joseph S.B. Mitchell is a SUNY Distinguished Professor in the Department of Applied Mathematics and Statistics at the State University of New York at Stony Brook. His research interests encompass computational geometry, algorithms and data structures, optimization, operations research, graphics and visualization, as well as computer-aided (geometric) design and manufacturing. He is associated with the AI Innovation Institute at Stony Brook, contributing to advancements in these fields through his academic and research activities.

Research topics

• Computer Science
• Artificial Intelligence
• Discrete mathematics
• Mathematics
• Mathematical analysis
• Computer vision
• Algorithm
• Programming language
• Combinatorics
• Geometry

Selected publications

• Approximating Maximum Independent Set for Rectangles in the Plane

  2022 · 17 citations

  1st authorCorresponding

  We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log\log n)$</tex> . The results are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursivel…

  DOI

• Computing Coordinated Motion Plans for Robot Swarms: The CG:SHOP Challenge 2021

  ACM Journal of Experimental Algorithmics · 2022 · 8 citations

  Senior authorCorresponding

  We give an overview of the 2021 Computational Geometry Challenge, which targeted the problem of optimally coordinating a set of robots by computing a family of collision-free trajectories for a set S of n pixel-shaped objects from a given start configuration to a desired target configuration.

  DOI

• Shortcut hulls: Vertex-restricted outer simplifications of polygons

  Computational Geometry · 2023-01-19 · 2 citations

  article
  PublisherDOI

• Provable Methods for Searching with an Imperfect Sensor

  2025-05-19 · 1 citations

  articleSenior author

  Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times bet…

  PublisherDOI

• Voluntary mobility clustering for epidemic control

  2025-11-03

  articleOpen access

  In case of a future pandemic, the mobility dynamics of a city can be controlled by intervening in the mobility patterns of people. Instead of hard quarantine policies, incentives can be designed that are compatible with people's preferences. At first, we distinguish mobility from the different types of locations for which distance matters. We match these types of locations in a way that maximizes the natural preference of people to visit the locations. We investigate different approaches for mat…

  PublisherOA PDFDOI

Recent grants

• Algorithmic Studies in Applied Geometry

  NSF · $200k · 2007–2010

• AF: Small: Approximation Algorithms for Geometric Network Optimization

  NSF · $451k · 2015–2019

• International Symposium on Computational Geometry (SOCG) 2015, Eindhoven, The Netherlands, June 22-25, 2015

  NSF · $15k · 2015–2016

Frequent coauthors

• Esther M. Arkin

  Hangzhou Dianzi University

  219 shared

• Valentin Polishchuk

  85 shared

• Sándor P. Fekete

  Technische Universität Braunschweig

  83 shared

• Steven Skiena

  53 shared

• Michael A. Bender

  Stony Brook University

  43 shared

• Alon Efrat

  Alexandru Ioan Cuza University

  35 shared

• Martin Held

  33 shared

• Erik D. Demaine

  33 shared

Similar researchers at Stony Brook University

• Michael R. Douglash-91
• Miriam Rafailovichh-84
• Ramana V Davulurih-75