BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Otfried Cheong appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We prove that in any strongly fan-planar drawing of a graph G the edges can be colored with at most three colors, such that no two edges of the same color cross. This implies that the thickness of strongly fan-planar graphs is at most three. If G is bipartite, then two colors suffice to color the edges in this way.
We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with $n$ vertices. We give exact algorithms that solve these problems in time $O(n^3)$. We also give $(1-\varepsilon)$-approximation algorithms that take time $O(\varepsilon^{-3/2}+ \varepsilon^{-1/2} \log n)$.
Given four congruent balls $A, B, C, D$ in $R^{d}$ that have disjoint interior and admit a line that intersects them in the order $ABCD$, we show that the distance between the centers of consecutive balls is smaller than the distance between the centers of $A$ and $D$. This allows us to give a new short proof that $n$ interior-disjoint congruent balls admit at most three geometric permutations, two if $n\ge 7$. We also make a conjecture that would imply that $n\geq 4$ such balls admit at most two geometric permutations, and show that if the conjecture is false, then there is a counter-example of a highly degenerate nature.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
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 seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(n log n)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G.
Given a set $S$ of points in the plane, a geometric network for $S$ is a graph $G$ with vertex set $S$ and straight edges. We consider a broadcasting situation, where one point $r \in S$ is a designated source. Given a dilation factor $δ$, we ask for a geometric network $G$ such that for every point $v \in S$ there is a path from $r$ to $v$ in $G$ of length at most $δ|rv|$, and such that the total edge length is minimized. We show that finding such a network of minimum total edge length is NP-hard, and give an approximation algorithm.
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). For two robot configurations $σ, σ'$, let $\ell(σ, σ')$ be the shortest bounded-curvature path from $σ$ to $σ'$. For $d \geq 0$, let $\ell(d)$ be the supremum of $\ell(σ, σ')$, over all pairs $(σ, σ')$ that are at Euclidean distance $d$. We study the function $\dub(d) = \ell(d) - d$, which expresses the difference between the bounded-curvature path length and the Euclidean distance of its endpoints. We show that $\dub(d)$ decreases monotonically from $\dub(0) = 7π/3$ to $\dub(\ds) = 2π$, and is constant for $d \geq \ds$. Here $\ds \approx 1.5874$. We describe pairs of configurations that exhibit the worst-case of $\dub(d)$ for every distance $d$.
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 distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log^3 n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k-1 connected components, but if one component is bounded, then it is equal to the entire region.
A line g is a transversal to a family F of convex polytopes in 3-dimensional space if it intersects every member of F. If, in addition, g is an isolated point of the space of line transversals to F, we say that F is a pinning of g. We show that any minimal pinning of a line by convex polytopes such that no face of a polytope is coplanar with the line has size at most eight. If, in addition, the polytopes are disjoint, then it has size at most six. We completely characterize configurations of disjoint polytopes that form minimal pinnings of a line.
Let $B$ be a point robot moving in the plane, whose path is constrained to forward motions with curvature at most one, and let $P$ be a convex polygon with $n$ vertices. Given a starting configuration (a location and a direction of travel) for $B$ inside $P$, we characterize the region of all points of $P$ that can be reached by $B$, and show that it has complexity $O(n)$. We give an $O(n^2)$ time algorithm to compute this region. We show that a point is reachable only if it can be reached by a path of type CCSCS, where C denotes a unit circle arc and S denotes a line segment.
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 give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n).
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 angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q of C is the minimum aperture angle of any x in C Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q of C with aperture angle approximation error (1 - 2/(k+1)) pi. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance sigma, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/(k+1) * sin(pi/(k+1)).
For two points $p$ and $q$ in the plane, a straight line $h$, called a highway, and a real $v>1$, we define the \emph{travel time} (also known as the \emph{city distance}) from $p$ and $q$ to be the time needed to traverse a quickest path from $p$ to $q$, where the distance is measured with speed $v$ on $h$ and with speed 1 in the underlying metric elsewhere. Given a set $S$ of $n$ points in the plane and a highway speed $v$, we consider the problem of finding a \emph{highway} that minimizes the maximum travel time over all pairs of points in $S$. If the orientation of the highway is fixed, the optimal highway can be computed in linear time, both for the $L_1$- and the Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal highway can be computed in $O(n^{2} \log n)$ time. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.
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 with each A_i touching A_0 for 1 <= i <= n.