Minimal Ellipsoid Circumscribing a Polytope Defined by a System of Linear Inequalities

In this paper, we will propose algorithms for calculating a minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities. If we know all vertices of the polytope and its cardinality is not very large, we can solve the problem in an efficient manner by a number of existent algorithms. However, when the polytope is defined by linear inequalities, these algorithms may not work since the cardinality of vertices may be huge. Based on a fact that vertices determining an ellipsoid are only a fraction of these vertices, we propose algorithms which iteratively calculate an ellipsoid which covers a subset of vertices. Numerical experiment shows that these algorithms perform well for polytopes of dimension up to seven.     

The generalized yolk point

The generalized yolk point is defined and solved using constructive geometric techniques. A numerical example illustrates the solution methodology and form of the associated size functional.     

On the robust assignment problem under a fixed number of cost scenarios

We investigate the complexity of the min-max assignment problem under a fixed number of scenarios. We prove that this problem is polynomial-time equivalent to the exact perfect matching problem in bipartite graphs, an infamous combinatorial optimization problem of unknown computational complexity.     

Non-interactive geometric probing: Reconstructing non-convex polygons

We address the problem of characterizing polygonal shapes that can be reconstructed from a class of scanners that have asymmetric resolution. We approach this problem using the methodology of non-interactive probing.

Laser raster scanners provide very high precision along the direction of a scan, but it is not practical to place scans very close to each other. A system capable of generating an omni-directional scan pattern can make a series of directional measurements sufficient to permit the reconstruction of a scanned polygon based on the position of edge crossings and the path of the scanning beam between edge crossings. We provide a procedure to reconstruct a polygon from such a data set, as well as a characterization of the shapes that can be reconstructed given a particular scan density. Our system applies to both concave and convex polygons, as well as to polygons containing holes.     

Minimum weight pseudo-triangulations

We consider the problem of computing a minimum weight pseudo-triangulation of a set of n points in the plane. We first present an -time algorithm that produces a pseudo-triangulation of weight which is shown to be asymptotically worst-case optimal, i.e., there exists a point set for which every pseudo-triangulation has weight , where is the weight of a minimum weight spanning tree of . We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon.     

I/O-efficient algorithms for computing planar geometric spanners

We present I/O-efficient algorithms for computing planar Steiner spanners for point sets and sets of polygonal obstacles in the plane.     

On the sum of distances along a circle

The arc distance between two points on a circle is their geodesic distance along the circle. We study the sum of the arc distances determined by n points on a circle, which is a useful measure of the evenness of scales and rhythms in music theory. We characterize the configurations with the maximum sum of arc distances by a balanced condition: for each line that goes through the circle center and touches no point, the numbers of points on each side of the line differ by at most one. When the points are restricted to lattice positions on a circle, we show that Toussaint's snap heuristic finds an optimal configuration. We derive closed-form formulas for the maximum sum of arc distances when the points are either allowed to move continuously on the circle or restricted to lattice positions. We also present a linear-time algorithm for computing the sum of arc distances when the points are presorted by the polar coordinates.     

Algebraic methods and arithmetic filtering for exact predicates on circle arcs

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs. We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants. This method allows the use of efficient arithmetic and filtering techniques leading to fast implementation as shown by the experimental results.     

Isoperimetric triangular enclosures with a fixed angle

In this paper, we study four variants of the famous isoperimetric problem. Given a set S of n > 2 points in the plane (in general position), we show how to compute in O(n ²) time, a triangle with maximum (or minimum) area enclosing S among all enclosing triangles with fixed perimeter and one fixed angle. We also show how to compute in O(n ²) time, a triangle with maximum (or minimum) perimeter enclosing S among all enclosing triangles with fixed area and one fixed angle. We also provide an Ω (n log n) lower bound for these problems in the algebraic computation tree model.     

The cyclic minimum correlation problem

For variables (x,y,z) in [0, 1]³, three functionsA(y,z),B(z,x),C(x,y), with values in [0, 1], are to be chosen to minimize the integral, over (x,y,z) in the unit cube, ofAB+BC+CA, subject to prescribed values for the integral of each function. It is shown that a minimum can be achieved by dividing each of thex,y,z intervals into three or fewer subintervals and taking each ofA,B,C as indicator function of the union of some of the nine (or fewer) rectangles into which this divides its domain. Several specializations and generalizations of this problem are given consideration. It can be considered as a decision problem with distributed information.     

A note on two fixed point problems

We extend the applicability of the Exterior Ellipsoid Algorithm for approximating n-dimensional fixed points of directionally nonexpanding functions. Such functions model many practical problems that cannot be formulated in the smaller class of globally nonexpanding functions. The upper bound 2n²ln(2/) on the number of function evaluations for finding -residual approximations to the fixed points remains the same for the larger class. We also present a modified version of a hybrid bisection-secant method for efficient approximation of univariate fixed point problems in combustion chemistry.     

Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion

In this paper a class of bottleneck combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing a finite number of cost vectors, called scenarios. In order to choose a solution the Ordered Weighted Averaging aggregation operator (OWA for short) is applied. The OWA operator generalizes traditional criteria in decision making under uncertainty such as the maximum, minimum, average, median, or Hurwicz criterion. New complexity and approximation results in this area are provided. These results are general and remain valid for many problems, in particular for a wide class of network problems.     

Computational aspects of cutting-plane algorithms for geometric programming problems

This paper presents the results of computational studies of the properties of cutting plane algorithms as applied to posynomial geometric programs. The four cutting planes studied represent the gradient method of Kelley and an extension to develop tangential cuts; the geometric inequality of Duffin and an extension to generate several cuts at each iteration. As a result of over 200 problem solutions, we will draw conclusions regarding the effectiveness of acceleration procedures, feasible and infeasible starting point, and the effect of the initial bounds on the variables. As a result of these experiments, certain cutting plane methods are seen to be attractive means of solving large scale geometric programs.This author's research was supported in part by the Center for the Study of Environmental Policy, The Pennsylvania State University.     

Covering moving points with anchored disks

Consider a set of mobile clients represented by n points in the plane moving at constant speed along n different straight lines. We study the problem of covering all mobile clients using a set of k disks centered at k fixed centers. Each disk exists only at one instant and while it does, covers any client within its coverage radius. The task is to select an activation time and a radius for each disk such that every mobile client is covered by at least one disk. In particular, we study the optimization problem of minimizing the maximum coverage radius. First we prove that, although the static version of the problem is polynomial, the kinetic version is NP-hard. Moreover, we show that the problem is not approximable by a constant factor (unless P = NP). We then present a generic framework to solve it for fixed values of k, which in turn allows us to solve more general optimization problems. Our algorithms are efficient for constant values of k.