Timothy M. Chan

activity

20242026

collaborators

Showing cs.CGShow all

5 papers · 1 filter

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