Ge Xia

activity

20112023

most citedThe Stretch Factor of the Delaunay Triangulation Is Less Than 1.998

73 citations · 80 across the 10 of their papers we have counts for

collaborators

12 papers

cs.DS2023

Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Jianer Chen, Qin Huang, Iyad Kanj +2

We present streaming algorithms for the graph $k$ -matching problem in both the insert-only and dynamic models. Our algorithms, with space complexity matching the best upper bounds,…

cs.CG2022

An $O (3.8 2^{k})$ Time FPT Algorithm for Convex Flip Distance

Haohong Li, Ge Xia

Let $P$ be a convex polygon in the plane, and let $T$ be a triangulation of $P$ . An edge $e$ in $T$ is called a diagonal if it is shared by two triangles in $T$ . A flip of a diagon…

cs.DS2021★ 1 cited

Optimal Streaming Algorithms for Graph Matching

Jianer Chen, Qin Huang, Iyad Kanj +1

We present parameterized streaming algorithms for the graph matching problem in both the dynamic and the insert-only models. For the dynamic streaming model, we present a one-pass…

cs.CG2020

Near-Optimal Algorithms for Point-Line Covering Problems

Jianer Chen, Qin Huang, Iyad Kanj +1

We study fundamental point-line covering problems in computational geometry, in which the input is a set $S$ of points in the plane. The first is the Rich Lines problem, which asks…

cs.CC2017★ 3 cited

The Complexity of Tree Partitioning

Zhao An, Qilong Feng, Iyad Kanj +1

Given a tree $T$ on $n$ vertices, and $k, b, s_{1}, \dots, s_{b} \in N$ , the Tree Partitioning problem asks if at most $k$ edges can be removed from $T$ so that the resulting componen…

cs.DS2014

Computing the flip distance between triangulations

Iyad Kanj, Eric Sedgwick, Ge Xia

Let $T$ be a triangulation of a set $P$ of $n$ points in the plane, and let $e$ be an edge shared by two triangles in $T$ such that the quadrilateral $Q$ forme…