Bit-index sort: A fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.

Logistics and the waste sector: a London case study

London has traditionally exported most of its waste to former mineral workings in surrounding counties for landfill. Many of these sites are being filled and opportunities for new sites are limited. Virtually all waste reprocessing and recycling facilities, with the exception of textile sorting and some facilities for glass and organic waste composting, are outside London. The Mayor of London's Vision for Waste in London is that by 2020, municipal waste should not compromise London’s future as a sustainable city. This will involve managing waste better, so that its impact on the local and global environment and on London communities, economy and health is minimised. The majority of waste and recyclable materials in London are currently collected and transported for recovery, disposal or reprocessing by road in large vehicles. Environmental costs include, adding to congestion, noise, energy usage, air pollution, and accidents. The Mayor is keen to increase recycling and reuse of waste materials in London, and to ensure that as more of London's waste is diverted away from landfill sites to recycling facilities. Several projects and initiatives have been established and these are reviewed in the paper.

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.