Two parallel algorithms for the convex hull problem in a two dimensional space

Two parallel algorithms for determining the convex hull of a set of data points in two dimensional space are presented. Both are suitable for MIMD parallel systems. The first is based on the strategy of divide-and-conquer, in which some simplest convex-hulls are generated first and then the final convex hull of all points is achieved by the processes of merging 2 sub-convex hulls. The second algorithm is by the process of picking up the points that are necessarily in the convex hull and discarding the points that are definitely not in the convex hull. Experimental results on a MIMD parallel system of 4 processors are analysed and presented.     

Using the method of interior points for computation of flow distribution in a hydraulic system with regulators

For hydraulic computations that take flow and pressure regulators into account, a little-known variant of the Newton method is used. Successive approximations belong to the interior of a set R specified by linear inequalities. In contrast to the base variant of the method of interior points, the Jacobian matrix is square. The solution of the problem of flow distribution is found on the boundary of R. The local convergence of the method considered is analyzed. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 173–178, July–August, 2000.     

On the shape of a set of points and lines in the plane

Detailed geometric models of the real world are in increasing demand. LiDAR data is appropriate to reconstruct urban models. In urban scenes, the individual surfaces can be reconstructed and connected to form the scene geometry. There are various methods for reconstructing the free‐form shape of a point sample on a single surface. However, these methods do not take the context of the surface into account. We present the guided α‐shape: an extension of the well known α‐shape that uses lines (guides) to indicate preferred locations for the boundary of the shape. The guided α‐shape uses (parts of) these lines as boundary where the points suggest that this is appropriate. We prove that the guided α‐shape can be constructed in O((n + m) log (n + m)) time, from an input of n points and m guides. We apply guided α‐shapes to urban reconstruction from LiDAR, where neighboring surfaces can be connected conveniently along their intersection lines into adjacent surfaces of a 3D model. We analyze guided α‐shapes of both synthetic and real data and show they are consistently better than α‐shapes for this application.     

On the impact of analyzing customer information and prioritizing in a service system

This paper examines prioritization in a service system and analyzes whether, in the presence of heterogeneous customers who have different needs and a costly sorting process, it pays to prioritize. In particular, in our model, sorting is costly because the task of gathering information to prioritize jobs consumes resources. We investigate a stylized model in which there are two classes of jobs — one whose waiting cost is high, called urgent, and the other whose waiting cost is low, called non-urgent. There are two types of employees, sorters, who collect information on a job and then decide whether it is urgent or non-urgent, and processors, who execute the job or provide the service. We begin by assuming that sorters categorize customers perfectly, and we relax this assumption later in the paper. We optimize two performance metrics, waiting costs (under a given budget) and total costs, and find the conditions under which prioritization is beneficial for these two metrics.     

On the transfer matrix of a neutral system: Characterizations of exponential stability in input—output terms

This paper investigates the stability of linear autonomous multivariable neutral systems from an input—output viewpoint. Several frequency-domain and input—output characterizations for exponential stability of neutral systems are given. We provide two examples which illustrate that the behaviour of neutral systems may be quite different from that of retarded systems. Moreover we give necessary and sufficient conditions for the transfer functions of a neutral system to belong to certain algebras of meromorphic functions introduced in this paper.     

On a method for solving a local boundary problem for a nonlinear stationary system with perturbations in the class of piecewise constant controls

The wide class of nonlinear stationary systems of ordinary differential equations taking into account restrictions on control and external perturbation is considered. An algorithm for constructing a discrete control function that guarantees the transfer of the systems from the initial state to the origin and an arbitrary neighborhood of the origin is proposed. A constructive sufficient condition of the Kalman type, in which the specified translation is possible, is obtained. The problem of robot‐manipulator control is considered and its numerical simulation is carried out.