Search

Many geometric computations have at their core the evaluation of the sign of the determinant of a matrix. A fast, failsafe determinant sign operation is often a key part of a robust implementation. While linear problems from 3D computational geometry usually require determinants no larger than six, non-linear problems involving algebraic curves and surfaces produce larger matrices. Furthermore, the matrix entries often exceed machine precision, while existing approaches focus on machine-precision matrices. In this paper, we describe a practical hybrid method for computing the sign of the determinant of matrices of order up to 60. The stages include a floating-point filter based on the singular value decomposition of a matrix, an adaptive-precision implementation of Gaussian elimination, and a standard modular arithmetic determinant algorithm. We demonstrate our method on a number of examples encountered while solving polynomial systems. [ABSTRACT FROM AUTHOR]

The static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to accomplish the delivery of a radiation prescription to a target tumor in the minimum amount of delivery time. Geometrically, the SLS problem can be formulated as a 3-D partition problem for which the 2-D problem of partitioning a polygonal domain (possibly with holes) into a minimum set of monotone polygons is a special case. In this paper, we present new geometric algorithms for a basic case of the 3-D SLS problem (which is also of clinical value) and for the general 3-D SLS problem. Our basic 3-D SLS algorithm, based on new geometric observations, produces guaranteed optimal quality solutions using O(1) Steiner points in polynomial time; the previously best known basic 3-D SLS algorithm gives optimal outputs only for the case without considering any Steiner points, and its time bound involves a multiplicative factor of a factorial function of the input. Our general 3-D SLS algorithm is based on our basic 3-D SLS algorithm and a polynomial time algorithm for partitioning a polygonal domain (possibly with holes) into a minimum set of x-monotone polygons, and has a fast running time. Experiments of our SLS algorithms and software in clinical settings have shown substantial improvements over the current most popular commercial treatment planning system and the most well-known SLS algorithm in medical literature. The radiotherapy plans produced by our software not only take significantly shorter delivery times, but also have a much better treatment quality. This proves the feasibility of our software and has led to its clinical applications at the Department of Radiation Oncology at the University of Maryland Medical Center. Some of our techniques and geometric procedures (e.g., for partitioning a polygonal domain into a minimum set of x-monotone polygons) are interesting in their own right. [ABSTRACT FROM AUTHOR]

In this paper, we study a 3D geometric problem originated from computing neural maps in the computational biology community: Given a set S of n points in 3D, compute k cylindrical segments (with different radii, orientations, lengths and no segment penetrates another) enclosing S such that the sum of their radii is minimized. There is no known result in this direction except when k=1. The general problem is strongly NP-hard and we obtain a polynomial time approximation scheme (PTAS) for any fixed k>1 in O(n3k-2/δ4k-3) time by returning k cylindrical segments with sum of radii at most (1+δ) of the corresponding optimal value, if exist. Our PTAS is built upon a simple (though slower) approximation algorithm for the case when k=1. [ABSTRACT FROM AUTHOR]