International Journal of Computational Geometry & Applications

Given a connected graph G=(V,E) with positive edge weights, define the distance d_G(u,v) between vertices u and v to be the length of a shortest path from u to v in G. A spanning subgraph G' of G is said to be a t-spanner for G if, for every pair of vertices u and v, d_G'(u,v)≤t·d_G(u,v). Consider a complete graph G whose vertex set is a set of n points in and whose edge weights are given by the L_p distance between respective points. Given input parameter ∊, 0<∊≤1, we show how to construct a (1+∊)-spanner for G containing edges in time. We apply this spanner to the construction of approximate minimum spanning trees.

We consider a rectilinear shortest path problem among weighted obstacles. Instead of restricting a path to totally avoid obstacles we allow a path to pass through them at extra costs. The extra costs are represented by the weights of the obstacles. We aim to find a shortest rectilinear path between two distinguished points among a set of weighted obstacles. The unweighted case is a special case of this problem when the weight of each obstacle is +∞. By using a graph-theoretical approach, we obtain two algorithms which run in O(n log² n) time and O(n log n) space and in O(n log^3/2 n) time and space, respectively, where n is the number of the vertices of the obstacles.

A set of parametric equations of an algebraic curve or surface is called normal, if all the points of the curve or the surface can be given by the parametric equations. In this paper, we present a method to decide whether a set of parametric equations is normal. In addition, we give some simple criteria for a set of parametric equations to be normal. As an application, we present a method to find normal parametric equations for conics. We also present a new method to find parametric equations for conicoids, and if the parametric equations found are not normal, the missing points can also be given.

In this paper, we discuss the problem of covering a convex rectilinear polygon with the minimum number of rectangles. The rectangles can overlap with each other. We show that this problem can be solved in linear time, which improves the previous O(n²) result proposed by Franzblau and Kleitman³. However, Franzblau and Kleitman's algorithm works for a larger class of polygons (vertically convex).

Given is a set S of n points, each colored with one of k≥3 colours. We say that a triangle defined by three points of S is 3-colored if its vertices have distinct colours. We prove in this paper that the problem of constructing the boundary of the union T(S) of all such 3-colored triangles can be done in optimal O(n log n) time.

Seven open problems are discussed. The problems are gathered from recent papers and from problems sessions at recent conferences.