Arrow Research search

Author name cluster

Siu-Wing Cheng

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers
2 author rows

Possible papers

28

STOC Conference 2025 Conference Paper

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time

  • Siu-Wing Cheng
  • Haoqiang Huang
  • Shuo Zhang 0034

Let τ and σ be two polygonal curves in ℝ d for any fixed d . Suppose that τ and σ have n and m vertices, respectively, and m ≤ n . While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of n c in strongly subquadratic time, for some constant c ∈(0,1). We present a randomized algorithm with running time O ( nm 0.99 log( n /ε)) that approximates the Fréchet distance within a factor of 7+ε, with a success probability at least 1−1/ n 6 . We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ε in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

Details

SODA Conference 2024 Conference Paper

Solving Fréchet Distance Problems by Algebraic Geometric Methods

  • Siu-Wing Cheng
  • Haoqiang Huang

We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let 𝕏 d m and 𝕏 d k be the spaces of all polygonal curves of m and k vertices in ℝ d, respectively. We assume that k ≤ m. Let be the set of ranges in 𝕏 d m for all possible metric balls of polygonal curves in 𝕏 d k under the Fréchet distance. We prove a nearly optimal bound of O(dk log( km )) on the VC dimension of the range space (𝕏 d m, ), improving on the previous O(d 2 k 2 log( dkm )) upper bound and approaching the current Ω( dk log k ) lower bound. Our upper bound also holds for the weak Fréchet distance. We also obtain exact solutions that are hitherto unknown for the curve simplification, range searching, nearest neighbor search, and distance oracle problems. * Research supported by the Research Grants Council, Hong Kong, China (project no. 16208923).

Details

SODA Conference 2023 Conference Paper

Curve Simplification and Clustering under Fréchet Distance

  • Siu-Wing Cheng
  • Haoqiang Huang

We present new approximation results on curve simplification and clustering under Fréchet distance. Let T = { t i: i ∈ [ n ]} be polygonal curves in ℝ d of m vertices each. Let ℓ be any integer from [ m ]. We study a generalized curve simplification problem: given error bounds δ i > 0 for i ∈ [ n ], find a curve σ of at most ℓ vertices such that d F (σ, t i ) ≤ δ i for i ∈ [ n ]. We present an algorithm that returns a null output or a curve σ of at most ℓ vertices such that d F (σ, τ i ) < δ i + εδ max for i ∈ [ n ], where δ max = max i ∈[ n ] δ i. If the output is null, there is no curve of at most ℓ vertices within a Frechet distance of δ i from τ i for i ∈ [ n ]. The running time is Õ ( n O (ℓ) · m O (ℓ 2 ) · ( d ℓ/ε) O(d ℓ). This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve τ to another curve σ, where the vertices of σ can be anywhere in ℝ d, so that d F (σ, τ) ≤ (1 + ε)δ and |σ| ≤ (1 + α) · min{| c |: d F (c, τ) ≤ δ} for any given δ > 0 and any fixed α, ε ∈ (0, 1). The running time is Õ ( m O (1/α) · ( d /(αε)) O(d /α) ). By combining our technique with some previous results in the literature, we obtain an approximation algorithm for ( k, ℓ)-median clustering. Given T, it computes a set Σ of k curves, each of ℓ vertices, such that is within a factor 1 + ε of the optimum with probability at least 1 — μ for any given μ, ε ∈ (0, 1). The running time is † The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 07809

Details

TCS Journal 2022 Journal Article

Multistage online maxmin allocation of indivisible entities

  • Siu-Wing Cheng

We consider an online allocation problem that involves a set P of n players and a set E of m indivisible entities over discrete time steps 1, 2, …, τ. At each time step t ∈ [ 1, τ ], for every entity e ∈ E, there is a restriction list L t ( e ) that prescribes the subset of players to whom e can be assigned and a non-negative value v t ( e, p ) of e to every player p ∈ P. The sets P and E are fixed beforehand. The sets L t ( ⋅ ) and values v t ( ⋅, ⋅ ) are given in an online fashion. An allocation is a distribution of E among P, and we are interested in the minimum total value of the entities received by a player according to the allocation. In the static case, it is NP-hard to find an optimal allocation the maximizes this minimum value. On the other hand, ρ-approximation algorithms have been developed for certain values of ρ ∈ ( 0, 1 ]. We propose a w-lookahead algorithm for the multistage online maxmin allocation problem for any fixed w ⩾ 1 in which the restriction lists and values of entities may change between time steps, and there is a fixed stability reward for an entity to be assigned to the same player from one time step to the next. The objective is to maximize the sum of the minimum values and stability rewards over the time steps 1, 2, …, τ. Our algorithm achieves a competitive ratio of ( 1 − c ) ρ, where c is the positive root of the equation w c 2 = ρ ( w + 1 ) ( 1 − c ). When w = 1, it is greater than ρ 4 ρ + 2 + ρ 10, which improves upon the previous ratio of ρ 4 ρ + 2 − 2 1 − τ ( 2 ρ + 1 ) obtained for the case of 1-lookahead.

Details DOI

TCS Journal 2021 Journal Article

Fitting a graph to one-dimensional data

  • Siu-Wing Cheng
  • Otfried Cheong
  • Taegyoung Lee
  • Zhengtong Ren

Given n data points in R d, an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regression problems. The graph proposed by Daitch, Kelner and Spielman (ICML 2009) can be computed by quadratic programming and hence in polynomial time. While a more efficient algorithm would be preferable, replacing quadratic programming is challenging even for the special case of points in one dimension. We develop a dynamic programming algorithm for this case that runs in O ( n 2 ) time under the Real-RAM model, where arithmetic on real numbers takes constant time.

Details DOI

TCS Journal 2015 Journal Article

Minimax regret 1-sink location problem in dynamic path networks

  • Yuya Higashikawa
  • John Augustine
  • Siu-Wing Cheng
  • Mordecai J. Golin
  • Naoki Katoh
  • Guanqun Ni
  • Bing Su
  • Yinfeng Xu

This paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location is defined as the minimum time to complete the evacuation for all supplies (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We propose an O ( n log ⁡ n ) time algorithm for the minimax regret 1-sink location problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.

Details DOI

SODA Conference 2015 Conference Paper

Triangulation Refinement and Approximate Shortest Paths in Weighted Regions

  • Siu-Wing Cheng
  • Jiongxin Jin
  • Antoine Vigneron

Let be a planar subdivision with n vertices. Each face of has a weight from [1, ρ ] ∪ {∞}. A path inside a face has cost equal to the product of its length and the face weight. In general, the cost of a path is the sum of the subpath costs in the faces intersected by the path. For any ε ∊ (0, 1), we present a fully polynomial-time approximation scheme that finds a (1 + ε )-approximate shortest path between two given points in in time, where k is the smallest integer such that the sum of the k smallest angles in is at least π. Therefore, our running time can be as small as if there are O (1) small angles and it is in the worst case. Our algorithm relies on a new triangulation refinement method, which produces a triangulation of size O ( n + k 2 ) such that no triangle has two angles less than min{π/(2 k ), π/12}.

Details

STOC Conference 2014 Conference Paper

Shortest paths on polyhedral surfaces and terrains

  • Siu-Wing Cheng
  • Jiongxin Jin

We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L 1 and L ∞ shortest paths on a polyhedral surface in O ( n 2 log 4 n ) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε )-approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O [EQUATION]. This is the first efficient PTAS for such a general setting of terrain navigation.

Details

SODA Conference 2013 Conference Paper

Approximate Shortest Descending Paths

  • Siu-Wing Cheng
  • Jiongxin Jin

We present an approximate algorithm for the shortest descending path (SDP) problem. Given a source s and a destination t in a polygonal terrain T, an SDP from s to t is a path in T of minimum Euclidean length subject to the constraint that the height decreases monotonically as we traverse that path from s to t. Given any ε ∊ (0, 1), our algorithm returns in O ( n 4 log( n /ε)) time a descending path of length at most 1 + ε times the optimum. This is the first algorithm whose running time is polynomial in n and log(1/ε) and independent of the terrain geometry.

Details

TCS Journal 2004 Journal Article

Competitive facility location: the Voronoi game

  • Hee-Kap Ahn
  • Siu-Wing Cheng
  • Otfried Cheong
  • Mordecai Golin
  • René van Oostrum

We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is then subdivided according to the nearest-neighbor rule, and the player whose points control the larger area wins. We present a winning strategy for the second player, where the arena is a circle or a line segment. We permit variations where players can play more than one point at a time, and show that the first player can ensure that the second player wins by an arbitrarily small margin.

Details DOI

TCS Journal 2001 Journal Article

On β-skeleton as a subgraph of the minimum weight triangulation

  • Siu-Wing Cheng
  • Yin-Feng Xu

Given a set S of n points in the plane, a triangulation is a maximal set of non-intersecting edges connecting the points in S. The weight of the triangulation is the sum of the lengths of the edges. In this paper, we show that for β>1/sin κ, the β-skeleton of S is a subgraph of a minimum weight triangulation of S, where κ=tan −1(3/ 2 3 )≈π/3. 1. There exists a four-point example such that the β-skeleton for β<1/sin(π/3) is not a subgraph of the minimum weight triangulation.

Details DOI

TCS Journal 2000 Journal Article

The Steiner tree problem for terminals on the boundary of a rectilinear polygon

  • Siu-Wing Cheng

Given a simple rectilinear polygon P with k sides and n terminals on its boundary, we present an O(k3n)-time algorithm to compute the minimal rectilinear Steiner tree lying inside P interconnecting the terminals. We obtain our result by proving structural properties of a selective set of minimal Steiner trees and exploiting them in a dynamic programming algorithm.

Details DOI

FOCS Conference 1990 Conference Paper

New Results on Dynamic Planar Point Location

  • Siu-Wing Cheng
  • Ravi Janardan

A point location scheme is presented for an n-vertex dynamic planar subdivision whose underlying graph is only required to be connected. The scheme uses O(n) space and yields an O(log/sup 2/n) query time and an O(log n) update time. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in O(k log(n+k)) (respectively, O(k log n)) time. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to O(log/sup 2/n log log n+k) time (or O(log n log log n+k) time for an alternative model of input), but at the expense of increasing the other time bounds slightly. All bounds are worst case. Additional results include a generalization to planar subdivisions consisting of algebraic segments of bounded degree and a persistent scheme for planar point location. >

Details
v2026.09.13