4 papers
Visibility Queries in Simple Polygons
Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla +6
Given a simple polygon with vertices, we consider the problem of constructing a data structure for visibility queries: for any query point , compute the visibility…
The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics
Henri Nikoleit, Ankit Anand, Anurag Murty Naredla +1
We demonstrate the power of human-LLM collaboration in tackling open problems in theoretical computer science. Focusing on combinatorial optimization, we refine outputs from the Fu…
Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
Jack Spalding-Jamieson, Anurag Murty Naredla
Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for the minimu…
Faster Approximation Algorithms for k-Center via Data Reduction
Arnold Filtser, Shaofeng H. -C. Jiang, Yi Li +4
We study efficient algorithms for the Euclidean -Center problem, focusing on the regime of large . We take the approach of data reduction by considering -coreset, which i…