Search

We consider two non-convex enclosing shapes with the minimum area; the L-shape and the quadrant hull. This paper proposes efficient algorithms computing each of two shapes enclosing a set of points with the minimum area over all orientations. The algorithms run in time quadratic in the number of given points by efficiently maintaining the set of extremal points. [ABSTRACT FROM AUTHOR]

Transportation networks model facilities for fast movement on the plane. A transportation network, together with its underlying distance, induces a new distance. Previously, only the Euclidean and the L1 distances have been considered as such underlying distances. However, this paper first considers distances induced by general distances and transportation networks, and present a unifying approach to compute Voronoi diagrams under such a general setting. With this approach, we show that an algorithm for convex distances can be easily obtained. [ABSTRACT FROM AUTHOR]

In casting, molten material is poured into the cavity of the cast and allowed to solidify. The cast has two main parts to be removed in opposite parting directions. To manufacture more complicated objects, the cast may also have a side core to be removed in a direction skewed to the parting directions. In this paper, given an object and the parting and side core directions, we give necessary and sufficient conditions to verify whether a cast can be constructed for these directions. In the case of polyhedral objects, we develop a discrete algorithm to perform the test in O(n3log n) time, where n is the object size. If the test result is positive, a cast with complexity O(n3) can be constructed within the same time bound. We also present an example to show that a cast may have Θ(n3) complexity in the worst case. Thus, the complexity of our cast is worst-case optimal. [ABSTRACT FROM AUTHOR]