5 citations · 17 across the 15 of their papers we have counts for
20 papers
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…
Fault Tolerance in Euclidean Committee Selection
Chinmay Sonar, Subhash Suri, Jie Xue
In the committee selection problem, the goal is to choose a subset of size from a set of candidates that collectively gives the best representation to a set of voters. We c…
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…
Clustering What Matters: Optimal Approximation for Clustering with Outliers
Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh +1
Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set of points and two integers and , the clustering with outliers aims…
Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space
Chinmay Sonar, Subhash Suri, Jie Xue
We consider multiwinner elections in Euclidean space using the minimax Chamberlin-Courant rule. In this setting, voters and candidates are embedded in a -dimensional Euclidean s…
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 (…
Enumerations of Universal Cycles for -Permutations
Zuling Chang, Jie Xue
Universal cycle for -permutations is a cyclic arrangement in which each -permutation appears exactly once as consecutive elements. Enumeration problem of universal cycles…
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +2
We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on -minor free graphs. In particular, we obtain the following resul…
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…