Arrow Research search

Author name cluster

Joseph S. B. Mitchell

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
1 author row

Possible papers

23

MFCS Conference 2025 Conference Paper

Guarding Offices with Maximum Dispersion

  • Sándor P. Fekete
  • Kai Kobbe
  • Dominik Krupke
  • Joseph S. B. Mitchell
  • Christian Rieck
  • Christian Scheffer

We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (r-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic L₁-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of 4 in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3 in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer [Christian Rieck and Christian Scheffer, 2024]. When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of 2+ε is NP-hard for any ε > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance 2. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15s.

Details

ICRA Conference 2025 Conference Paper

Provable Methods for Searching with an Imperfect Sensor

  • Prahlad Narasimhan Kasthurirangan
  • Linh Nguyen 0004
  • Michael Perk
  • Nilanjan Chakraborty
  • Joseph S. B. Mitchell

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 between points (e. g. , based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to characterize their performance.

Details

FOCS Conference 2023 Conference Paper

Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon

  • Reilly Browne
  • Prahlad Narasimhan Kasthurirangan
  • Joseph S. B. Mitchell
  • Valentin Polishchuk

Given a simple polygon P, the minimum convex cover problem seeks to cover P with the fewest convex polygons that lie within P. The maximum hidden set problem seeks to place within P a maximum cardinality set of points no two of which see each other. We give constant factor approximation algorithms for both problems. Previously, the best approximation factor for the minimum convex cover was logarithmic; for the maximum hidden set problem, no approximation algorithm was known.

Details

FOCS Conference 2021 Conference Paper

Approximating Maximum Independent Set for Rectangles in the Plane

  • Joseph S. B. Mitchell

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 $O(\log\log n)$. 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 recursively partitioned into a constant number of such faces.

Details

SODA Conference 2013 Conference Paper

Approximating Watchman Routes

  • Joseph S. B. Mitchell

Given a connected polygonal domain P, the watchman route problem is to compute a shortest path or tour for a mobile guard (the “watchman”) that is required to see every point of P. While the watchman route problem is polynomially solvable in simple polygons, it is known to be NP-hard in polygons with holes. We present the first polynomial-time approximation algorithm for the watchman route problem in polygonal domains. Our algorithm has an approximation factor O (log 2 n ). Further, we prove that the problem cannot be approximated in polynomial time to within a factor of c log n, for a constant c > 0, assuming that P≠NP.

Details

STOC Conference 2003 Conference Paper

Touring a sequence of polygons

  • Moshe Dror
  • Alon Efrat
  • Anna Lubiw
  • Joseph S. B. Mitchell

Given a sequence of k polygons in the plane, a start point s , and a target point, t , we seek a shortest path that starts at s , visits in order each of the polygons, and ends at t . If the polygons are disjoint and convex, we give an algorithm running in time O(kn log (n/k)) , where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk 2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m) , where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons" problem is NP-hard.The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n 2 log n) time and the watchman route problem (through a fixed point s ) in time O(n 3 log n) , compared with the previous time bounds of O(n 3 ) and O(n 4 ) , respectively.

Details

FOCS Conference 1992 Conference Paper

Computing a Shortest k-Link Path in a Polygon

  • Joseph S. B. Mitchell
  • Christine D. Piatko
  • Esther M. Arkin

The authors consider the problem of finding a shortest polygonal path from s to t within a simple polygon P, subject to the restriction that the path have at most k links (edges). They give an algorithm to compute a k-link path with length at most (1 + epsilon ) times the length of a shortest k-link path, for any error tolerance epsilon >0. The algorithm runs in time O(n/sup 3/k/sup 3/ log (Hk/ epsilon /sup 1/k/)), where N is the largest integer coordinate among the n vertices of P. They also study the more general problem of approximating shortest k-link paths in polygons with holes. In this case, they give an algorithm that returns a path with at most 2k links and length at most that of a shortest k-link path; the running time is O(kE/sup 2/), where E is the number of edges in the visibility graph. Finally, they study the bicriteria path problem in which the two criteria are link length and 'total turn' (the integral of mod Delta theta mod along a path). They obtain in an exact polynomial-time algorithm for polygons with holes. >

Details

ICRA Conference 1984 Conference Paper

Algorithm of navigation for a mobile robot

  • David M. Keirsey
  • E. Koch
  • J. McKisson
  • Alex Meystel
  • Joseph S. B. Mitchell

This study describes the theoretical and practical aspects of the design and computer simulation of a heuristic based navigation algorithm. An algorithm is developed which provides a convenient testing system for generalized navigation strategies on a fixed map which may be known or unknown to a system. A variety of maps are simulated and the navigation results are compared.

Details
v2026.09.13