Computing optimal scalings by parametric network algorithms

Asymmetric scaling of a square matrixA 0 is a matrix of the formXAX ^–1 whereX is a nonnegative, nonsingular, diagonal matrix having the same dimension ofA. Anasymmetric scaling of a rectangular matrixB 0 is a matrix of the formXBY ^–1 whereX andY are nonnegative, nonsingular, diagonal matrices having appropriate dimensions. We consider two objectives in selecting a symmetric scaling of a given matrix. The first is to select a scalingA of a given matrixA such that the maximal absolute value of the elements ofA is lesser or equal that of any other corresponding scaling ofA. The second is to select a scalingB of a given matrixB such that the maximal absolute value of ratios of nonzero elements ofB is lesser or equal that of any other corresponding scaling ofB. We also consider the problem of finding an optimal asymmetric scaling under the maximal ratio criterion (the maximal element criterion is, of course, trivial in this case). We show that these problems can be converted to parametric network problems which can be solved by corresponding algorithms.This research was supported by NSF Grant ECS-83-10213.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

An exact construction of digital convex polygons with minimal diameter

Given a natural number n, an exact formula is derived for the minimal possible size MD(n) of a square grid, in which a digital convex n-gon can be inscribed. An exact construction of a digital convex n-gon which can be inscribed into a square grid of size MD(n) is also given.     

Computing shortest heterochromatic monotone routes

Given a set of n points on the plane colored with k≤n colors, the Trip Planning Problem asks for the shortest path visiting the k colors. It is a well-known NP-hard problem. We show that under some natural constraints on the path, the problem can be solved in polynomial time.     

Computing a Minimum Weight Triangulation of a Sparse Point Set*

Investigating the minimum weight triangulation of a point set with constraint is an important approach for seeking the ultimate solution of the minimum weight triangulation problem. In this paper, we consider the minimum weight triangulation of a sparse point set, and present an O(n ⁴) algorithm to compute a triangulation of such a set. The property of sparse point set can be converted into a new sufficient condition for finding subgraphs of the minimum weight triangulation. A special point set is exhibited to show that our new subgraph of minimum weight triangulation cannot be found by any currently known methods.     

A geometric proof of the combinatorial bounds for the number of optimal solutions for the Euclidean 2-center problem

We provide lower and upper bounds for γ(n), the number of optimal solutions for the two-center problem: “Given a set S of n points in the real plane, find two closed discs whose union contains all of the points such that the radius of the larger disc is minimized.”The main result of the paper shows the matching upper and lower bounds for the two-center problem and demonstrates that γ(n)=n.     

Quadrilaterizing an Orthogonal Polygon in Parallel

We consider the problem of quadrilaterizing an orthogonal polygon P, that is to decompose P into nonoverlapping convex quadrangles without adding new vertices. In this paper we present a CREW-algorithm for this problem which runs in O(log N) time using Θ(N/log N) processors if the rectangle decomposition of P is given, and Θ(N) processors if not. Furthermore we will show that the latter result is optimal if the polygon is allowed to contain holes.     

Computing a maxian point of a simple rectilinear polygon

Let P be a simple rectilinear polygon with n vertices. There are k points in P. The maxian problem is to locate a single facility in P so as to maximize the sum of its distance from it to the k points. We present an O((n×k)logn) time algorithm for this problem.     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

Finding optimal volume subintervals with k points and calculating the star discrepancy are NP-hard problems

The well-known star discrepancy is a common measure for the uniformity of point distributions. It is used, e.g., in multivariate integration, pseudo random number generation, experimental design, statistics, or computer graphics.     

Pointwise maximum principle for convex optimal control problems with mixed control-phase variable inequality constraints

The validity of a global pointwise maximum principle is proved for a class of convex optimal control problems with mixed control-phase variable inequality constraints. No compatibility hypotheses are required, and singular multipliers are avoided.     

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.     

平面有限点集中的最大面积六边形

若平面上的有限点集构成凸多边形的顶点集,则称此有限点集处于凸位置令P表示平面上处于凸位置的有限点集,研究了P的子集所确定的凸六边形的面积与CH(P)面积比值的最大值问题.     

Covering a Convex Polygon by Triangles

According to a theorem of A. V. Bogomolnaya, F. L. Nazarov and S. E. Rukshin, if n points are given inside a convex n-gon, then the points and the sides of the polygon can be numbered from 1 to n so that the triangles spanned by the ith point and the ith side(i=1....,n ) cover the polygon. In this paper, we prove that the same can be done without assuming that the given points are inside the convex n-gon. We also show that in the general case at least [(n/3)] mutually nonoverlapping triangles can be constructed in the same manner.