Cartographic line simplification and polygon CSG formulæ in O(n log n) time

A constructive solid geometry (CSG) conversion for a polygon takes a list of vertices and produces a formula representing the polygon as an intersection and union of primitive halfspaces. The cartographers' favorite line simplification algorithm recursively selects from a list of data points those to be used to represent a linear feature, such as a coastline, on a map. By using a data structure that maintains convex hulls of polygonal lines under splits, both were known to have O(n log n) time solutions in the worst-case. This paper shows that both are easier than sorting by presenting an O(n log^* n) algorithm for maintaining convex hulls under splits at extreme points. It opens the question of whether there are practical, linear-time solutions to these problems.     

Some results on the convex hull of finitely many convex sets

A better than quadratic estimate is given for the volume of the convex hull of points on Hadamard manifolds with pinched curvature. It was known previously that the volume is bounded by some polynomial in . The estimate comes from the study of the convex hull of finitely many convex sets on Hadamard manifolds.

     

Categorical Properties of Probabilistic Convergence Spaces

The purpose of this paper is to discuss some categorical properties of probabilistic convergence spaces. Its main theses are: (1) the construct P-PrTop of probabilistic pretopological spaces is the extensional topological hull of the construct FTPcs of FT-diagonal probabilistic convergence spaces for every triangular norm T; (2) the construct P-PsTop of probabilistic pseudotopological spaces is the topological universe hull of FTPcs for every triangular norm T.     

Method of orienting curves for determining the convex hull of a finite set of points in the plane

In this article, we present an efficient algorithm to determine the convex hull of a finite planar set using the idea of the Method of Orienting Curves (introduced by Phu in Zur Lösung einer regulären Aufgabenklasse der optimalen Steuerung in Großen mittels Orientierungskurven, Optimization, 18 (1987), pp. 65–81, for solving optimal control problems with state constraints). The convex hull is determined by parts of orienting lines and a final line. Two advantages of this algorithm over some variations of Graham's convex hull algorithm are presented.     

The polynomial numerical hull of a matrix and algorithms for computing the numerical range

Let A be an n × n matrix. In this paper we discuss theoretical properties of the polynomial numerical hull of A of degree one and assemble them into three algorithms to computing the numerical range of A.     

On the convex hull of the simple integer recourse objective function

We consider the objective function of a simple integer recourse problem with fixed technology matrix.Using properties of the expected value function, we prove a relation between the convex hull of this function and the expected value function of a continuous simple recourse program.We present an algorithm to compute the convex hull of the expected value function in case of discrete right-hand side random variables. Allowing for restrictions on the first stage decision variables, this result is then extended to the convex hull of the objective function.Supported by the National Operations Research Network in the Netherlands (LNMB).     

Group decisions I. In arbitrary spaces of fuzzy binary relations

This article solves the problem of finding a set of group decisions that satisfy the classical Pareto unanimity principle for the case of initial data represented as fuzzy relations of individual preference. The solution proceeds from results obtained in studying the structure of convex (in the sense defined here) sets and their convex hulls. In the first part that study is carried out for spaces of arbitrary fuzzy binary relations.     

A polynomial algorithm for one problem of guillotine cutting

We consider the problem of guillotine cutting a rectangular sheet into two rectangular pieces without rotations. The question is whether there exists a cutting pattern with given numbers of occurrences of both rectangular pieces. A polynomial time algorithm is described to construct the convex hull of solutions to this problem.     

An introduction to preconvexity spaces

Axioms are given for a preconvexity space and certain consequences obtained. In particular, it is shown that in a very natural way, a preconvexity on a space yields an abstract convexity space in much the same manner as a proximity yields a topological space. This revised version was published online in June 2006 with corrections to the Cover Date.     

Design of group decisions II. In spaces of partial order fuzzy relations

For the case of initial data in the problem of group choice represented as fuzzy partial orderings two problems are solved: (1) design of a set group decisions which satisfy the Pareto unanimity principlle and stay ‘halfway’ between initial relations and (2) design of a unique group decision.     

A realization of graph associahedra

Given any finite graph, we offer a simple realization of its corresponding graph associahedron polytope using integer coordinates.     

一秩算子和三角代数

Abstract, In this paper, a necessary condition for a maximal triangular algebra to be closed is given, A necessary and sufficient condition for a maxima] triangular algebra to he strongly reducible is obtained,     

关于Brandt半群共轭包的结构

在本文中，我们给出了Ｂｒａｎｄｔ半群Ｓ的共轭包Ψ（Ｓ）的刻划，同时也给出Ψ（Ｓ）的全逆子半群Ｔ（Ｓ）的刻划，利用这些结果，我们证明Ｔ（Ｓ）在Ψ（Ｓ）中是自共轭的．     

On a Constrained Optimal Location Algorithm

In problems of optimal location, one seeks a position or location that optimizes a particular objective function; this objective function typically relates location and distances to a fixed point set. When one's search is restricted to a given set, we refer to this as a constrained optimal location problem. For a finite point set A, there exist numerous finite algorithms to solve optimal location problems. In this paper we demonstrate how an algorithm, solving optimal location problems in inner-product spaces, can be modified to solve certain constrained optimal location problems. We then apply this modification to a particularly simple (and easily implemented) algorithm and investigate the complexity of the result. In particular we improve a known estimate from exponential to polynomial.     

Network flows and non-guillotine cutting patterns

Up till now there has been no exact and effective algorithm for the problem of finding optimal cutting patterns of rectangles which are not restricted to those with the ‘guillotine’ property. This problem can be interpreted in a resource constrained scheduling context. The contribution of this paper to this topic is a good characterization of the flow functions and graphs corresponding to cutting patterns.     

A constant-time parallel algorithm for computing convex hulls

The convex hull of a finite set of points in the plane can be computed in constant time using a polynomial number of processors.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC - A3336.     

Concave functions,blaschke products,and polygonal mappings

We consider the class Co(p) of all conformal maps of the unit disk onto the exterior of a bounded convex set. We prove that the triangle mappings, i.e., the functions that map the unit disk onto the exterior of a triangle, are among the extreme points of the closed convex hull of Co(p). Moreover, we prove a conjecture on the closed convex hull of Co(p) for all p ∈ (0, 1) which had partially been proved by the authors for some values of p ∈ (0, 1).     

Some properties of convex hulls generated by homogeneous Poisson point processes in an unbounded convex domain

LetC(A) be the convex hull generated by a Poisson point process in an unbounded convex setA. A representation ofAC(A) as the union of curvilinear triangles with independent areas is established. In the case whenA is a cone the properties of the representation are examined more completely. It is also indicated how to simulateC(A) directly without first simulating the process itself.