5 citations · 17 across the 15 of their papers we have counts for
15 papers · 1 filter
Approximating Convex Hulls via Range Queries
T. Schibler, J. Xue, J. Zhu
Recently, motivated by the rapid increase of the data size in various applications, Monemizadeh [APPROX'23] and Driemel, Monemizadeh, Oh, Staals, and Woodruff [SoCG'25] studied geo…
Minimum-Membership Geometric Set Cover, Revisited
Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1
We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set of points and a set $\m…
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh +2
Suppose we are given a pair of points and a set of geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (…
Dynamic Geometric Set Cover, Revisited
Timothy M. Chan, Qizheng He, Subhash Suri +1
Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may b…
Dynamic geometric set cover and hitting set
Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri +2
We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) op…
Range closest-pair search in higher dimensions
Timothy M. Chan, Saladi Rahul, Jie Xue
Range closest-pair (RCP) search is a range-search variant of the classical closest-pair problem, which aims to store a given set of points into some space-efficient data struct…
Improved Algorithms for the Bichromatic Two-Center Problem for Pairs of Points
Haitao Wang, Jie Xue
We consider a bichromatic two-center problem for pairs of points. Given a set of pairs of points in the plane, for every pair, we want to assign a red color to one point an…
Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
Haitao Wang, Jie Xue
We revisit a classical graph-theoretic problem, the \textit{single-source shortest-path} (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic)…
Colored range closest-pair problem under general distance functions
Jie Xue
The range closest-pair (RCP) problem is the range-search version of the classical closest-pair problem, which aims to store a given dataset of points in some data structure such th…
Searching for the closest-pair in a query translate
Jie Xue, Yuan Li, Saladi Rahul +1
We consider a range-search variant of the closest-pair problem. Let be a fixed shape in the plane. We are interested in storing a given set of points in the plane i…
New bounds for range closest-pair problems
Jie Xue, Yuan Li, Saladi Rahul +1
Given a dataset of points in , the range closest-pair (RCP) problem aims to preprocess into a data structure such that when a query range is specified, th…
On the expected diameter, width, and complexity of a stochastic convex-hull
Jie Xue, Yuan Li, Ravi Janardan
We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of points in each of which has a…
Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces
Jie Xue, Yuan Li
Let be a tree space (or tree network) represented by a weighted tree with vertices, and be a set of stochastic points in , each of which has a fixed location wit…
On Dominance-Free Samples of a (Colored) Stochastic Dataset
Jie Xue, Yuan Li
A point is said to dominate another point if the coordinate of is greater than or equal to the coordinate of in every dimension. A…
On the Separability of Stochastic Geometric Objects, with Applications
Jie Xue, Yuan Li, Ravi Janardan
In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint/multipoint uncertainty models. Let be a give…