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.

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.

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.

Accessibility instruments for planning practice: A review of European experiences

Although a large body of literature has been produced on the theoretical definitions and measurements of accessibility, the extent to which such indicators are used in planning practice is less clear. This research explores the gap between theory and application by seeking to understand what the new wave of accessibility instruments (AIs) prepared for spatial and transport planning practice purports to offer the users of AIs. Starting from the question of how urban and transport planners are designing AIs, the article analyzes and describes the AIs developed over the last decade (mainly in Europe), offering a structured overview and a clear categorization of how accessibility measures can be applied. The paper identifies AI characteristics, and considers their usability, based on AI developer perceptions.

Accessibility Instrument Survey

This chapter presents the main results of the Accessibility Instrument Survey (AIS), collecting basic information on each of the accessibility instruments reviewed in this report (for more detail on these Instruments see Chapter 3). The aim of the survey was to enable quick, objective and comparable overviews of each of the reviewed accessibility instruments. The information collected will enable the categorization of accessibility instruments present in this research, aiming to be a reference for future categorization of accessibility instruments for planning practice. These categories will support the analysis of the coverage of accessibility instruments in this research, i.e., identify how representative this research is across different accessibility instrument types. In addition, these will be used to analyse the characteristics and concerns which most frequently underlie the development of accessibility instruments. Finally, the survey also collects developer’s perceptions on the usefulness of their accessibility instruments in planning practice, enabling the first insight into the main research question of this COST Action, although limited to the developer’s point of view. In summary, the results of the survey will be used for four purposes: Development of an accessibility instrument sheet for each accessibility instrument summarizing its main characteristics (Appendix A); Identify the coverage of accessibility instrument types present in this research (Section 4.3.1) discussing the representativeness of this Action; Provide a glimpse on the characteristics and concerns which most frequently underlie the development of accessibility instruments (Section 4.3.2); Provide a first insight into the perceived usefulness of accessibility instruments in planning practice from the point of view of the developer (Section 4.3.2 and Section 4.3.3). The next section provides an overview of the Survey describing the information collected. This section also describes the development process of this survey including data collection, dates and means. The results of the survey are analysed in the third section starting with a discussion on the coverage of accessibility instruments reviewed by this research (Section 4.3.1), identifying accessibility measure types which are represented and which are absent. This discussion is accompanied by the presentation of the main categories of accessibility instruments from the perspective of the end user. These categories try to summarize the main concerns planning practitioners are expected to have when searching for an accessibility instrument and is built upon some of the information collected by the survey. Following, the third section also presents a general analysis of the results (Section 4.3.2), focussing on the dominant characteristics of the accessibility instruments reviewed and on the developer’s perception of the usefulness their instrument will have for end users. The section ends with a brief cross analysis of results (Section 4.3.3) trying to identify relationships between accessibility instrument characteristics and perceptions of usefulness by developers. The fourth and last section presents the main conclusions of this study.

Evaluating the Business Impact of Social Science: a report to the ESRC

This report presents the main findings from a project entitled ‘Evaluating the Business Impact of Social Science', commissioned by the Economic and Social Research Council (ESRC) and undertaken by a team of researchers from the University of Hull. In brief, the project involved an examination of the processes through which social science research and related activities impact upon business (defined broadly to incorporate large and small private sector businesses as well as social enterprises, but excluding public sector organisations) in relation to three of the UK’s leading business/management schools that have received significant amounts of ESRC funding in recent years: Cardiff Business School, Lancaster University Management School, and Warwick Business School

New Principles in Planning Evaluation

Maintaining and enhancing living conditions in cities through a combination of physical planning and environmental management is a newly emerging focus of governments around the world. For example, local governments seek to insulate sensitive land uses such as residential areas from environmentally intrusive activities such as major transport facilities and manufacturing. Regional governments protect water quality and natural habitat by enforcing pollution controls and regulating the location of growth. Some national governments fund acquisition of strategically important sites, facilitate the renewal of brown fields, and even develop integrated environmental quality plans. This book provides recently developed and tested methods for assessing the strengths and weaknesses of planning and policy options. Several contributions focus on new substantive areas of concern in planning evaluation, including environmental justice and sustainable urban development. Applications of evaluation in several planning contexts are demonstrated, and special problems that these pose are assessed. Several chapters address how to communicate the process and results to several stakeholder groups, and how to engage these groups in the evaluation process. Each chapter employs a realworld case in practice, thus dealing with the complexity of applying planning evaluation, and providing practical advice useful in similar situations.

Place-Based Evaluation for Infrastructure and Spatial Projects: An Introduction

This book brings together experts in the fields of spatial planning, landuse and infrastructure management to explore the emerging agenda of spatially-oriented integrated evaluation. It weaves together the latest theories, case studies, methods, policy and practice to examine and assess the values, impacts, benefits and the overall success in integrated land-use management. In doing so, the book clarifies the nature and roles of evaluation and puts forward guidance for future policy and practice.

Place-Based Evaluation for Integrated Land-Use Management

This book brings together experts in the fields of spatial planning, landuse and infrastructure management to explore the emerging agenda of spatially-oriented integrated evaluation. It weaves together the latest theories, case studies, methods, policy and practice to examine and assess the values, impacts, benefits and the overall success in integrated land-use management. In doing so, the book clarifies the nature and roles of evaluation and puts forward guidance for future policy and practice.

Evaluation for Participation and Sustainability in Planning

‘Evaluation for Participation and Sustainability in Planning’ is the title of a new book edited by Johan Woltjer and his colleagues Angela Hull, Ernest Alexander, and Abdul Khakee. The book addresses the evaluation of planning interventions from several perspectives (social, economic, environmental). Specifically, the attention is focused on: - how evaluation is used in planning practice, including the choice of indicators or the criteria to evaluate participation; - the introduction of new kinds of information, such as measuring the cumulative effects or bringing criteria on capability and well-being into play; - alternative ways of collecting and presenting information, through using GIS or focusing on strategic environmental awareness and ‘hotspots’; and - understanding how strategic planning objectives are implemented in local practice.