International Journal of Computational Geometry & Applications

Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum criteria with respect to L₁- and L₂-metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We present efficient algorithms for the 1-joint versions of the problem and fully polynomial-time approximation schemes for the general k-joint versions.

This paper investigates geometric and algorithmic properties of the Voronoi diagram for a transportation network on the Euclidean plane. In the presence of a transportation network, the distance is measured as the length of the shortest (time) path. In doing so, we introduce a needle, a generalized Voronoi site. We present an O(nm² + m³ + nm log n) algorithm to compute the Voronoi diagram for a transportation network on the Euclidean plane, where n is the number of given sites and m is the complexity of the given transportation network. Moreover, in the case that the roads in a transportation network have only a constant number of directions and speeds, we propose two algorithms; one needs O(nm + m² + n log n) time with O(m(n + m)) space and the other O(nm log n + m²log m) time with O(n + m) space.

We study the problem of maintaining a (1 + ∊)-factor approximation of the diameter of a stream of points under the sliding window model. In one dimension, we give a simple algorithm that only needs to store points at any time, where the parameter R denotes the "spread" of the point set. This bound is optimal and improves Feigenbaum, Kannan, and Zhang's recent solution by two logarithmic factors. We then extend our one-dimensional algorithm to higher constant dimensions and, at the same time, correct an error in the previous solution. In high nonconstant dimensions, we also observe a constant-factor approximation algorithm that requires sublinear space. Related optimization problems, such as the width, are also considered in the two-dimensional case.

Edelsbrunner et al. defined a framework of shape deformations with shapes bounded by skin manifold. We prove that the infinitely many synthesized shapes in the deformation sequence share finitely many common Voronoi complexes. Therefore, we propose a new algorithm to compute the common Voronoi complexes efficiently for the deformations, and use these common complexes to compute the synthesized shapes in real time. This makes generating, visualizing, and customizing shape deformations feasible.

The 3-D static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to deliver a prescribed radiation dose to a target tumor accurately and efficiently. The treatment time and machine delivery error are two crucial factors to the solution (i.e., a treatment plan) for the SLS problem. In this paper, we prove that the 3-D SLS problem is NP-hard, and present the first ever algorithm for the 3-D SLS problem that can determine a tradeoff between the treatment time and machine delivery error (also called the "tongue-and-groove" error in medical literature). Our new 3-D SLS algorithm with error control gives the users (e.g., physicians) the option of specifying a machine delivery error bound, and subject to the given error bound, the algorithm computes a treatment plan with the minimum treatment time. We formulate the SLS problem with error control as computing a k-weight shortest path in a directed graph and build the graph by computing g-matchings and minimum cost flows. Further, we extend our 3-D SLS algorithm to all the popular radiotherapy machine models with different constraints. In our extensions, we model the SLS problems for some of the radiotherapy systems as computing a minimum g-path cover of a directed acyclic graph. We implemented our new 3-D SLS algorithm suite and conducted an extensive comparison study with commercial planning systems and well-known algorithms in medical literature. Some of our experimental results based on real medical data are presented.

Let P be a polygon, possibly with holes. We define a witness set W to be a set of points in P such that if any (prospective) guard set G guards W, then it is guaranteed that G guards P. Not all polygons admit a finite witness set. If a finite minimal witness set exists, then it cannot contain any witness in the interior of P, all witnesses must lie on the boundary of P, and there can be at most one witness in the interior of every edge. We give an algorithm to compute a minimum size witness set for P in O(n²log n) time, if such a set exists, or to report the non-existence within the same time bounds. We also outline two algorithms that use a witness set for P to test whether a (prospective) guard set sees all points in P.

We present approximation algorithms for cutting out a polygon P with n vertices from another convex polygon Q with m vertices by line cuts and ray cuts. For line cuts we require both P and Q are convex while for ray cuts we require Q is convex and P is ray cuttable. Our results answer a number of open problems and are either the first solutions or significantly improve over previously known solutions. For the line cutting version, we prove a key property that leads to a simple, constant factor approximation algorithm. For the ray cutting version, we prove it is possible to compute in almost linear time a cutting sequence that is an O(log² n)-factor approximation of an optimal cutting sequence. No algorithms were previously known for the ray cutting version.

A drawing of a plane graph is called an inner rectangular drawing if every edge is drawn as a horizontal or vertical line segment so that every inner face is a rectangle. In this paper we show that a plane graph G has an inner rectangular drawing D if and only if a new bipartite graph constructed from G has a perfect matching. We also show that D can be found in time O(n^1.5/ log n) if G has n vertices and a sketch of the outer face is prescribed, that is, all the convex outer vertices and concave ones are prescribed.

Given a planar triangulation all of whose faces are initially white, we study the problem of colouring the faces black one by one so that the boundary between black and white faces as well as the number of connected black and white regions are small at all times. We call such a colouring sequence of the triangles a flooding. We prove that a flooding with boundary size and regions can be computed in time. We also prove that it is in general impossible to guarantee boundary size , for any ∊ > 0, and a number of regions that is o(log n), where n is the number of faces of the triangulation.