Timothy M. Chan

activity

20242026

collaborators

7 papers

cs.CG2026

Shaving Two Logs for Discrete and Continuous Fréchet Distance

Timothy M Chan, Isaac M Hair

We revisit the classical computational geometry problem of computing the exact (discrete or continuous) Fréchet distance between two given polygonal curves with $n$ vertices in a c…

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 $Ω (n lo g n)$ lower bound in the algebraic comp…

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…

cs.CG2025

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.CG2024

Convex Polygon Containment: Improving Quadratic to Near Linear Time

Timothy M. Chan, Isaac M. Hair

We revisit a standard polygon containment problem: given a convex $k$ -gon $P$ and a convex $n$ -gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotati…

cs.CG2024

Enclosing Points with Geometric Objects

Timothy M. Chan, Qizheng He, Jie Xue

Let $X$ be a set of points in $R^{2}$ and $O$ be a set of geometric objects in $R^{2}$ , where $∣ X ∣ + ∣ O ∣ = n$ . We study the problem of computing a…