Preconditioning 2D Integer Data for Fast Convex Hull Computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

In Support of the Matrix Language Frame Model: Evidence from Igbo-English Intrasentential Codeswitching

This paper explores the morphosyntactic features of mixed nominal expressions in a sample of empirical Igbo-English intrasentential codeswitching data (i.e. codeswitching within a bilingual clause) in terms of the Matrix Language Frame (MLF) model. Since both Igbo and English differ in the relative order of head and complement within the nominal argument phrase, the analysed data seem appropriate for testing the veracity of the principal assumption underpinning the MLF model: the notion that the two languages (in our case Igbo and English) participating in codeswitching do not both contribute equally to the morphosyntactic frame of a mixed constituent. As it turns out, the findings provide both empirical and quantitative support for the basic theoretical view that there is a Matrix Language (ML) versus Embedded Language (EL) hierarchy in classic codeswitching as predicted by the MLF model because both Igbo and English do not simultaneously satisfy the roles of the ML in Igbo-English codeswitching.

Igbo-English Intrasentential Codeswitching and the Matrix Language Frame model

This paper uses some data from Igbo-English intrasentential codeswitching involving mixed nominal expressions to test the Matrix Language Frame (MLF) model. The MLF model is one of the most highly influential frameworks used successfully in the study of grammatical aspects of codeswitching. Three principles associated with it, the Matrix Language Principle, the Asymmetry Principle and the Uniform Structure Principle, were tested on data collected from informal conversations by educated adult Igbo-English bilinguals resident in Port Harcourt. The results of the analyses suggest general support for the three principles and for identifying Igbo-English as a ‘classic’ case of codeswitching.

An Empirical Evaluation of Preconditioning Data for Accelerating Convex Hull Computations

The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.

An Empirical Evaluation of Preconditioning Data for Accelerating Convex Hull Computations

The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.