International Journal of Computational Geometry & Applications

We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(n log n) time lower bounds for separability by means of strips, wedges, wedges with apices on a given line, fixed-slopes double wedges, and triangles, which match the complexity of the existing algorithms, and therefore prove their optimality.

The method described here relies on interval arithmetic and graph theory to compute guaranteed coverings of strange attractors like Hénon attractor. It copes with infinite intervals, using either a geometric method or a new directed projective interval arithmetic.

Given two convex polygons P and Q in the plane that are free to translate and rotate, a convex packing of them is the convex hull of a placement of P and a placement of Q whose interiors do not intersect. A minimum area convex packing of P and Q is one whose area is minimized. The problem of designing a deterministic algorithm for finding a minimum area convex packing of two convex polygons has remained open. We address this problem by first studying the contact configurations between P and Q and their algebraic structures. Crucial geometric and algebraic properties on the area function are then derived and analyzed which enable us to successfully discretize the search space. This discretization, together with a delicate algorithmic design and careful complexity analysis, allows us to develop an efficient O((n + m)nm) time deterministic algorithm for finding a true minimum area convex packing of P and Q, where n and m are the numbers of vertices of P and Q, respectively.

In this paper we first modify a widely used discrete Laplace-Beltrami operator proposed by Meyer et al over triangular surfaces, and then we show that the modified discrete operator has some convergence properties over the triangulated spheres. A sequence of spherical triangulations which is optimal in certain sense and leads to smaller truncation error of the discrete Laplace-Beltrami operator is constructed. Optimal hierarchical spherical triangulations are also given. Truncation error bounds of the discrete Laplace-Beltrami operator over the constructed triangulations are provided.