6 papers
Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
Sujoy Bhore, Timothy M. Chan
We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geo…
Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii +4
We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant , one could constru…
Fully Dynamic Geometric Vertex Cover and Matching
Sujoy Bhore, Timothy M. Chan
In this work, we study two fundamental graph optimization problems, minimum vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection graphs of geometric objects,…
On Colorful Vertex and Edge Cover Problems
Sayan Bandyapadhyay, Aritra Banik, Sujoy Bhore
In this paper, we study two generalizations of Vertex Cover and Edge Cover, namely Colorful Vertex Cover and Colorful Edge Cover. In the Colorful Vertex Cover problem, given an …
Dynamic Euclidean Bottleneck Matching
A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi
A fundamental question in computational geometry is for a set of input points in the Euclidean space, that is subject to discrete changes (insertion/deletion of points at each time…
On Streaming Algorithms for Geometric Independent Set and Clique
Sujoy Bhore, Fabian Klute, Jelle J. Oostveen
We study the maximum geometric independent set and clique problems in the streaming model. Given a collection of geometric objects arriving in an insertion only stream, the aim is…