17909513
Determining an optimal penetration among weighted regions in two and three dimensions
We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3-D spaces. This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering. Our algorithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penetration problem can be reduced to solving O(n2(d−1)) instances of certain special types of non-linear optimization problems, where n is the total number of vertices of the regions. We also give implementation results of our 2-D algorithms.
8713870
Optimal Terrain Construction Problems and Applications
in Intensity-Modulated Radiation Therapy
AbstractIn this paper we study several rectilinear terrain construction
problems, which model the leaf sequencing problems in
intensity-modulated radiation therapy (IMRT).
We present a novel unified approach
based on geometric techniques for solving these terrain
construction problems. Our ideas include formulating the terrain
construction problems as computing shortest paths in a weighted directed
graph and building the graph by computing optimal bipartite matchings on various geometric objects
subject to specific constraints of each of the problems. Further,
since we need to compute optimal bipartite matchings on many sets
of geometric objects, we use techniques for computing such
matchings in a batch fashion to speed up these matching
computations. Our approach leads to the first algorithms for several leaf
sequencing problems in IMRT that are practically fast and guarantee
 an output which is optimal for a large sub-class of solutions. The previously known leaf
sequencing algorithms which are currently used in radiation therapy practice
are all heuristics that do not guarantee any good
quality of the output solutions and may run in a long time.
Our implementation
results show that our terrain construction algorithms run very
fast on real medical data (all under few seconds).
9160894
Geometric algorithms for static leaf sequencing problems in radiation therapy
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 Steiner points in polynomial time; the previously best known basic 3-D SLS algorithm gives optimal outputs only for the case without 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 and comparisons using real medical data and on a real radiotherapy machine have shown that our 3-D SLS algorithms and software produce treatment plans that use significantly shorter delivery time and give better treatment quality than the current most popular commercial treatment planning system and the most well-known SLS algorithm. Some of our techniques and geometric procedures (e.g., for the problem of partitioning a polygonal domain into a minimum set of x-monotone polygons) are interesting in their own right.
2863452
Optimal Polygon Cover Problems and Applications
Polygon cover problems are important in several applied areas, such as material layout, layered manufacturing, radiation therapy and radiosurgery, etc. In this paper, we study three optimal polygon cover problems: monotone polygon cover among obstacles, star-shaped polygon cover among obstacles, and strip cover for trapezoidalized polygons. Based on some interesting geometric observations, we develop efficient algorithms for solving these problems. The complexity bounds of our monotone cover and star-shaped cover algorithms are comparable to those of the previously best known algorithms for simpler cases of the problems without considering obstacles. Our strip cover algorithm improves the quality of the previously best known solutions.
42223547
Pairwise Data Clustering and Applications
Data clustering is an important theoretical topic and a sharp tool for various applications. Its main objective is to partition a given data set into clusters such that the data within the same cluster are "more" similar to each other with respect to certain measures. In this paper, we study the pairwise data clustering problem with pairwise similarity/ dissimilarity measures that need not satisfy the triangle inequality. By using a criterion, called the minimum normalized cut, we model the pairwise data clustering problem as a graph partition problem. The graph partition problem based on minimizing the normalized cut is known to be NP-hard. We present a ((4 + o(1)) ln n)-approximation polynomial time algorithm for the minimum normalized cut problem. We also give a more efficient algorithm for this problem by sacrificing the approximation ratio slightly. Further, our scheme achieves a ((2 + o(1)) ln n)- approximation polynomial time algorithm for computing the sparsest cuts in edge-weighted and vertex-weighted undirected graphs, improving the previously best known approximation ratio by a constant factor.
27904596
Segmenting Doughnut-Shaped Objects in Medical Images
Image segmentation with specific constraints has found applications in several areas such as biomedical image analysis and data mining. In this paper, we study the problem of segmenting doughnut-shaped and smooth objects in 2-D medical images. Image objects of these shapes are often studied in medical applications. We present an O(IJU(U − L)logJlog(U − L)) time algorithm, where the size of the input 2-D image is I× J, M is the smoothness parameter with 1 ≤ M ≤ J, and L and U are the thickness parameters specifying the thickness between two border contours of a doughnut-shaped object. Previous approaches for solving this segmentation problem are computationally expensive and/or need a lot of user interference. Our algorithm improves the straightforward dynamic programming algorithm by a factor of \(O(\frac{J(U-L)M^2}{U{\rm log}J{\rm log}(U-L)})\). We explore some interesting observations, which make possible to apply the divide-and-conquer strategy combined with dynamic programming. Our algorithm is also based on computing optimal paths in an implicitly represented graph.
40889509
New Double-Byte Error-Correcting Codes for Memory Systems
Double-byte error-correcting codes over GF(q) were constructed by Dumer (1981, 1988, 1992, 1995), which have the parameters n=q/sup m-1/, r/spl les/2m+[m-1/3], m=2, 3, ..., when q is even, and have the parameters n=q/sup m/, r/spl les/2m+[m/3]+1, m=2; 3, ..., when q is odd, respectively. We construct a class of double-byte error-correcting codes over GF(2/sup i/), which have the following parameters: n=q/sup m/, r/spl les/2m+[m/3]+1, m=3, 4, .... So our constructions reduce the code redundancy of Dumer by one symbol, and we eliminate the disparity in code redundancies obtained for even and odd q. A decoding procedure for our codes is also considered.
7000665
Multiple Agents Moving Target Search
Traditional single-agent search algorithms usually make simplifying assumptions (single search agent, stationary target, complete knowledge of the state, and sufficient time). There are algorithms for relaxing one or two of these constraints; in this paper we want to relax all four. The application domain is to have multiple search agents cooperate to pursue and capture a moving target. Agents are allowed to communicate with each other. For solving Multiple Agents Moving Target (MAMT) applications, we present a framework for specifying a family of suitable search algorithms. This paper investigates several effective approaches for solving problem instances in this domain.
11758071
Algorithms for optimal multi-resolution quantization
Multi-resolution quantization is a way of constructing a progressively refinable description of a discrete random variable. The underlying discrete optimization problem is to minimize an expected distortion over all refinement levels weighted by the probability or importance of the descriptions of different resolutions. This research is motivated by the application of multimedia communications via variable-rate channels. We propose an O(rN2) time and O(N2 log N) space algorithm to design a minimum-distortion quantizer of r levels for a random variable drawn from an alphabet of size N. It is shown that for a very large class of distortion measures the objective function of optimal multi-resolution quantization satisfies the convex Monge property. The efficiency of the proposed algorithm hinges on the convex Monge property. But our algorithm is simpler (even though of the same asymptotic complexity) than the well-known SMAWK fast matrix search technique, which is the best existing solution to the quantization problem. For exponential random variables our approach leads to a solution of even lower complexity: O(rN) time and O(N log N) space, which outperforms all the known algorithms for optimal quantization in both multi- and single-resolution cases. We also generalize the multi-resolution quantization problem to a graph problem, for which our algorithm offers an efficient solution.
26409739
Guest Editors' Introduction
36354030
Globally optimal uneven error-protected packetization of scalable code streams
In this paper, we present a family of new algorithms for rate-fidelity optimal packetization of scalable source bit streams with uneven error protection. In the most general setting where no assumption is made on the probability function of packet loss or on the rate-fidelity function of the scalable code stream, one of our algorithms can find the globally optimal solution to the problem in O(N/sup 2/L/sup 2/) time, compared to a previously obtained O(N/sup 3/L/sup 2/) complexity, where N is the number of packets and L is the packet payload size. If the rate-fidelity function of the input is convex, the time complexity can be reduced to O(NL/sup 2/) for a class of erasure channels, including channels for which the probability function of losing n packets is monotonically decreasing in n and independent erasure channels with packet erasure rate no larger than N/2(N + 1). Furthermore, our O(NL/sup 2/) algorithm for the convex case can be modified to rind an approximation solution for the general case. All of our algorithms do away with the expediency of fractional bit allocation, a limitation of some existing algorithms.