Output-sensitive results on convex hulls,extreme points,and related problems

We use known data structures for ray-shooting and linear-programming queries to derive new output-sensitive results on convex hulls, extreme points, and related problems. We show that thef-face convex hull of ann-point setP in a fixed dimensiond≥2 can be constructed in time; this is optimal if for some sufficiently large constantK. We also show that theh extreme points ofP can be computed in time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers ofP inO(n ^2−γ) time for any constant . Finally, we obtain improved time bounds for other problems including levels in arrangements and linear programming with few violated constraints. In all of our algorithms the input is assumed to be in general position. This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship.     

Constrained minimax approximation and optimal preconditioned for Toeplitz matrices

A good preconditioner is extremely important in order for the conjugate gradients method to converge quickly. In the case of Toeplitz matrices, a number of recent studies were made to relate approximation of functions to good preconditioners. In this paper, we present a new result relating the quality of the Toeplitz preconditionerC for the Toeplitz matrixT to the Chebyshev norm (f– g)/f, wheref and g are the generating functions forT andC, respectively. In particular, the construction of band-Toeplitz preconditioners becomes a linear minimax approximation problem. The case whenf has zeros (but is nonnegative) is especially interesting and the corresponding approximation problem becomes constrained. We show how the Remez algorithm can be modified to handle the constraints. Numerical experiments confirming the theoretical results are presented.     

Ion-selective electrodes in organic analysis-determination of xanthate

A PVC membrane xanthate-selective electrode has been developed for the direct determination of xanthates of primary and secondary alcohols. The xanthate electrode is highly selective and exhibits a Nernstian response in the range 5.0 x 10(-2)-7.1 x 10(-5)M xanthate with a slope of 58.6 mV per concentration decade. The electrode has a wide working pH range (5.0-11.5), a fast response time (less than 30 sec) and is stable for at least two months.