International Journal of Computational Geometry & Applications

CAT(0) metric spaces and hyperbolic spaces play an important role in combinatorial and geometric group theory. In this paper, we present efficient algorithms for distance problems in CAT(0) planar complexes. First of all, we present an algorithm for answering single-point distance queries in a CAT(0) planar complex. Namely, we show that for a CAT(0) planar complex with n vertices, one can construct in O(n²log n) time a data structure of size O(n²) so that, given a point , the shortest path γ(x, y) between x and the query point y can be computed in linear time. Our second algorithm computes the convex hull of a finite set of points in a CAT(0) planar complex. This algorithm is based on Toussaint's algorithm for computing the convex hull of a finite set of points in a simple polygon and it constructs the convex hull of a set of k points in O(n²log n + nk log k) time, using a data structure of size O(n² + k).

Unistable polyhedra are in equilibrium on only one of their faces. The smallest known homogeneous unistable polyhedron to date has 18 faces. Using a new optimization algorithm, we have found a unistable polyhedron with only 14 faces, which we believe to be a lower bound. Despite the simplicity of the formulation, computers were never successfully used for solving this problem due to the seemingly insurmountable dimensionality of the underlying mathematical apparatus. We introduce new optimization approaches designed to overcome the problem's intractability and discuss its significance to other application areas. We also mathematically prove the unistable property of the found bodies using rational arithmetic. Surprisingly enough, all of our computer-generated unistable polyhedra look similar to the human eye, providing important insights into the nature of the problem.

Watermarking techniques for vector graphics dislocate vertices in order to embed imperceptible, yet detectable, statistical features into the input data. The embedding process may result in a change of the topology of the input data, e.g., by introducing self-intersections, which is undesirable or even disastrous for many applications. In this paper we present a watermarking framework for two-dimensional vector graphics that employs conventional watermarking techniques but still provides the guarantee that the topology of the input data is preserved. The geometric part of this framework computes so-called maximum perturbation regions (MPR) of vertices. We propose two efficient algorithms to compute MPRs based on Voronoi diagrams and constrained triangulations. Furthermore, we present two algorithms to conditionally correct the watermarked data in order to increase the watermark embedding capacity and still guarantee topological correctness. While we focus on the watermarking of input formed by straight-line segments, one of our approaches can also be extended to circular arcs. We conclude the paper by demonstrating and analyzing the applicability of our framework in conjunction with two well-known watermarking techniques.