Author name cluster

Otfried Cheong

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.

3 papers

1 author row

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 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 2003 Journal Article

Computing farthest neighbors on a convex polytope

Otfried Cheong
Chan-Su Shin
Antoine Vigneron

Let N be a set of n points in convex position in R 3. The farthest point Voronoi diagram of~N partitions~R 3 into n convex cells. We consider the intersection~G(N) of the diagram with the boundary of the convex hull of N. We give an algorithm that computes an implicit representation of G(N) in expected O(n log 2 n) time. More precisely, we compute the combinatorial structure of G(N), the coordinates of its vertices, and the equation of the plane defining each edge of G(N). The algorithm allows us to solve the all-pairs farthest neighbor problem for N in expected time O(n log 2 n), and to perform farthest-neighbor queries on N in O(log 2 n) time with high probability.

Details DOI