23 citations · 67 across the 33 of their papers we have counts for
24 papers · 1 filter
Better Late than Never: the Complexity of Arrangements of Polyhedra
Boris Aronov, Sang Won Bae, Sergio Cabello +4
Let be the subdivision of induced by convex polyhedra having facets in total. We prove that has combinatorial complexity $O(m^{\l…
Geometric Matching and Bottleneck Problems
Sergio Cabello, Siu-Wing Cheng, Otfried Cheong +1
Let be a set of at most points and let be a set of at most geometric ranges, such as for example disks or rectangles, where each has an associated supply…
Packing d-dimensional balls into a d+1-dimensional container
Helmut Alt, Sergio Cabello, Otfried Cheong +2
In this article, we consider the problems of finding in dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex b…
Fitting a Graph to One-Dimensional Data
Siu-Wing Cheng, Otfried Cheong, Taegyoung Lee +1
Given n data points in R^d, an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regresssion problems. The gra…
Placing your Coins on a Shelf
Helmut Alt, Kevin Buchin, Steven Chaplick +4
We consider the problem of packing a family of disks "on a shelf", that is, such that each disk touches the -axis from above and such that no two disks overlap. We prove that th…
Covering many points with a small-area box
Mark de Berg, Sergio Cabello, Otfried Cheong +2
Let be a set of points in the plane. We show how to find, for a given integer , the smallest-area axis-parallel rectangle that covers points of in $O(nk^2 \log…
Weight Balancing on Boundaries
Luis Barba, Otfried Cheong, Michael Gene Dobbins +8
Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, that is, wh…
The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions
Boris Aronov, Otfried Cheong, Michael Gene Dobbins +1
We show that the union of translates of a convex body in can have holes in the worst case, where a hole in a set is a connected component of $\mathb…
Finding Largest Rectangles in Convex Polygons
Sergio Cabello, Otfried Cheong, Christian Knauer +1
We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with vertices. We…
On the Number of Edges of Fan-Crossing Free Graphs
Otfried Cheong, Sariel Har-Peled, Heuna Kim +1
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges , such that have a common endpoint and cros…
A Generalization of the Convex Kakeya Problem
Hee-Kap Ahn, Sang Won Bae, Otfried Cheong +3
Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be se…
Single-Source Dilation-Bounded Minimum Spanning Trees
Otfried Cheong, Changryeol Lee
Given a set of points in the plane, a geometric network for is a graph with vertex set and straight edges. We consider a broadcasting situation, where one point $r…
The Cost of Bounded Curvature
Hyo-Sil Kim, Otfried Cheong
We study the motion-planning problem for a car-like robot whose turning radius is bounded from below by one and which is allowed to move in the forward direction only (Dubins car).…
Reachability by Paths of Bounded Curvature in a Convex Polygon
Hee-Kap Ahn, Otfried Cheong, Jirí Matoušek +1
Let be a point robot moving in the plane, whose path is constrained to forward motions with curvature at most one, and let be a convex polygon with vertices. Given a st…
Farthest-Polygon Voronoi Diagrams
Otfried Cheong, Hazel Everett, Marc Glisse +5
Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distan…
Computation of Spatial Skyline Points
Binay Bhattacharya, Arijit Bishnu, Otfried Cheong +3
We discuss a method of finding skyline or non-dominated sites in a set of point sites with respect to a set of points. A site is non-dominated if and only…
Lower Bounds for Pinning Lines by Balls
Otfried Cheong, Xavier Goaoc, Andreas Holmsen
A line L is a transversal to a family F of convex objects in R^d if it intersects every member of F. In this paper we show that for every integer d>2 there exists a family of 2d-1…
Reverse nearest neighbor queries in fixed dimension
Otfried Cheong, Antoine Vigneron, Juyoung Yon
Reverse nearest neighbor queries are defined as follows: Given an input point-set P, and a query point q, find all the points p in P whose nearest point in P U {q} \ {p} is q. We g…
Constructing Optimal Highways
Hee-Kap Ahn, Helmut Alt, Tetsuo Asano +7
For two points and in the plane, a straight line , called a highway, and a real , we define the \emph{travel time} (also known as the \emph{city distance}) from …
Computing a Minimum-Dilation Spanning Tree is NP-hard
Otfried Cheong, Herman Haverkort, Mira Lee
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum fac…
Aperture-Angle and Hausdorff-Approximation of Convex Figures
Hee-Kap Ahn, Sang Won Bae, Otfried Cheong +1
The aperture angle alpha(x, Q) of a point x not in Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture ang…
The Hadwiger Number of Jordan Regions is Unbounded
Otfried Cheong, Mira Lee
We show that for every n > 0 there is a planar topological disk A_0 and n translates A_1, A_2, ..., A_n of A_0 such that the interiors of A_0, ... A_n are pairwise disjoint, but wi…
Hadwiger and Helly-type theorems for disjoint unit spheres
Otfried Cheong, Xavier Goaoc, Andreas Holmsen +1
We prove Helly-type theorems for line transversals to disjoint unit balls in . In particular, we show that a family of disjoint unit balls in has a line…
Sparse geometric graphs with small dilation
Boris Aronov, Mark de Berg, Otfried Cheong +4
Given a set S of n points in R^D, and an integer k such that 0 <= k < n, we show that a geometric graph with vertex set S, at most n - 1 + k edges, maximum degree five, and dilatio…