Communications of the ACM

Linear-size nonobtuse triangulation of polygons

We give an algorithm for triangulating n-vertex polygonal regions (with holes) so that no angle in the final triangulation measures more than &pgr;/2. The number of triangles in the triangulation is only O(n), improving a previous bound of O(n2), and the worst-case running time is O(nlog2n). The basic technique used in the algorithm, recursive subdivision by disks, is new and may have wider application in mesh generation. We also report on an implementation of our algorithm.

Kinetic data structures for all nearest neighbors and closest pair in the plane

This paper presents a kinetic data structure (KDS) for solutions to the all nearest neighbors problem and the closest pair problem in the plane. For a set P of n moving points where the trajectory of each point is an algebraic function of constant maximum degree s, our kinetic algorithm uses O(n) space and O(n log n) preprocessing time, and processes O(n²β²_2s+2(n)log n) events with total processing time O(n²β²_2s+2(n)log² n), where β_s(n) is an extremely slow-growing function. In terms of the KDS performance criteria, our KDS is efficient, responsive (in an amortized sense), and compact.

Our deterministic kinetic algorithm for the all nearest neighbors problem improves by an O(log² n) factor the previous randomized kinetic algorithm by Agarwal, Kaplan, and Sharir. The improvement is obtained by using a new sparse graph representation, the Pie Delaunay graph, to reduce the problem to one-dimensional range searching, as opposed to using two-dimensional range searching as in the previous work.

Quantum clustering algorithms

By the term "quantization", we refer to the process of using quantum mechanics in order to improve a classical algorithm, usually by making it go faster. In this paper, we initiate the idea of quantizing clustering algorithms by using variations on a celebrated quantum algorithm due to Grover. After having introduced this novel approach to unsupervised learning, we illustrate it with a quantized version of three standard algorithms: divisive clustering, k-medians and an algorithm for the construction of a neighbourhood graph. We obtain a significant speedup compared to the classical approach.

Mining optimized association rules for numeric attributes

Scalability, generalization and coevolution -- experimental comparisons applied to automated facility layout planning

Several practical problems in industry are difficult to optimize, both in terms of scalability and representation. Heuristics designed by domain experts are frequently applied to such problems. However, designing optimized heuristics can be a non-trivial task. One such difficult problem is the Facility Layout Problem (FLP) which is concerned with the allocation of activities to space. This paper is concerned with the block layout problem, where the activities require a fixed size and shape (modules). This problem is commonly divided into two sub problems; one of creating an initial feasible layout and one of improving the layout by interchanging the location of activities. We investigate how to extract novel heuristics for the FLP by applying an approach called Cooperative Coevolutionary Gene Expression Programming (CCGEP). By taking advantage of the natural problem decomposition, one species evolves heuristics for pre-scheduling, and another for allocating the activities onto the plant. An experimental, comparative approach investigates various features of the CCGEP approach. The results show that the evolved heuristics converge to suboptimal solutions as the problem size grows. However, coevolution has a positive effect on optimization of single problem instances. Expensive fitness evaluations may be limited by evolving generalized heuristics applicable to unseen fitness cases of arbitrary sizes.

The computer background of incoming freshman: looking for emerging trends

As part of a longitudinal study begun in 1985, incoming Bentley College freshmen were asked to complete questionnaires about their pre-college computer experience. Although nearly all students came from high schools with computers and more than 80% of them had studied BASIC, just under half had used a word processor. Even fewer (less than 20%) had used either a spreadsheet or a database management system, though the actual percentage has risen over the three years for which data exist. The increase in the number of schools teaching Pascal noticed between 1984 and 1985 persisted in 1986. However, though nearly 46% of the schools from which 1986 graduates came taught Pascal, only half that percentage actually studied the language. Almost half the students used computers outside school during their high school years, but most of that use involved playing games.

Optimal Expected-Time Algorithms for Closest Point Problems

Journal of Data and Information Quality (JDIQ): Volume 3 Issue 2, May 2012

Bias and scalability in evolutionary development

The introduction of a genotype-phenotype map modelled on biological development can potentially improve the scalability of evolutionary algorithms. Previous work by Gordon and Bentley demonstrated that such a model can be used to evolve patterns that map to useful but small phenotypes. This paper uses the same model to generate much larger patterns covering arrays of up to 64x64 cells. The results show that the model's performance is generally comparable to similar development-based systems [12, 14], and with some measures outperforms them. Additionally the inherent biases of the model are explored, such as the need to use symmetry-breaking initial conditions which some other models do not require. This exploration yields a set of guidelines that suggest what kinds of problem the model is suited to exploring.

SearchMessenger: Exploring the Use of Search and Card Sharing in a Messaging Application

Previous work creating systems for collaborative search has mainly focused on solutions for the desktop. However, as the majority of web use moves to mobile phones, few systems have been created on this platform to support collaboration around search results. Mobile search is often a collaborative activity where the input of a group is sought before making a decision to purchase something, visit a venue, or book a ticket. However, currently search and messaging applications are separate, creating frustrating copy-and-paste interactions and uninformative blue links or OpenGraph cards in messages. We built the Search Messenger system to support both finding and sharing search results, in the form of rich, interactive cards, directly within a mobile messaging system. After building the system, we conducted a two-week field study exploring how 14 participants used the system in their daily lives. We report on our findings and implications for future mobile applications that embed functionality in messaging.