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.

An investigation of container train service provision and load factors in Great Britain

The continued growth in the volume of international trade poses considerable economic and sustainability challenges, particularly as transport routes become more congested and concern grows about the role of transport movements in accelerating climate change. Rail freight plays a major role in the inland transport of containers passing through the main British container ports, and potentially could play a more significant role in the future. However, there is little detailed understanding of the nature of this particular rail market, especially in terms its current operating efficiency. This paper examines container train service provision to/from the four main ports, based on analysis of a representative survey of more than 500 container trains between February and August 2007. The extent to which the existing capacity is utilised is presented, and scenarios by which the number of containers carried could be increased without requiring additional train service provision are modelled, to identify the theoretical potential for greater rail volumes. Finally, the paper identifies the challenges involved in achieving higher load factors, emphasising the importance both of wider supply chain considerations and government policy decision-making.

Development of a knowledge sharing framework for improving the testing processes in global product development

As identified by Griffin (1997) and Kahn (2012), manufacturing organisations typically improve their market position by accelerating their product development (PD) cycles. One method for achieving this is to reduce the time taken to design, test and validate new products, so that they can reach the end customer before competition. This paper adds to existing research on PD testing procedures by reporting on an exploratory investigation carried out in a UK-based manufacturing plant. We explore the organisational and managerial factors that contribute to the time spent on testing of new products during development. The investigation consisted of three sections, viz. observations and process modelling, utilisation metrics and a questionnaire-based investigation, from which a proposed framework to improve and reduce the PD time cycle is presented. This research focuses specifically on the improvement of the utilisation of product testing facilities and the links to its main internal stakeholders - PD engineers.