Timothy M. Chan

collaborators

4 papers

cs.CG2026

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Timothy M. Chan, Isaac M. Hair

Given two convex polygons $P$ and $Q$ with $n$ and $m$ edges, the maximum overlap problem is to find a translation of $P$ that maximizes the area of its intersection with $Q$ . We g…

cs.CG2026

Computing Planar Convex Hulls with a Promise

Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan +5

Computing the convex hull of a planar $n$ -point set $P$ is one of the most fundamental problems in computational geometry. It has an $I^c ◯ (n lo g n)$ lower bound in the algebraic com…

cs.CG2026

Delaunay Triangulations with Predictions

Sergio Cabello, Timothy M. Chan, Panos Giannopoulos

We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set $P$ of $n$ poi…

cs.DS2026

Derandomizing Pseudopolynomial Algorithms for Subset Sum

Timothy M. Chan

We reexamine the classical subset sum problem: given a set $X$ of $n$ positive integers and a number $t$ , decide whether there exists a subset of $X$ that sums to $t$ ; or more gene…