Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing

We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons.     

The Topology of Transportation Networks: A Comparison Between Different Economies

This paper presents an analysis of the topology of transportation networks within different systems of cities. Urban entities and their components are complex systems by their nature; there is no central force that affects their spatial structure. Thus, we study transportation networks within different countries as complex networks. Based on the above, we consider cities as nodes, while direct air and railways routes represent the links. We present characteristics of these networks including their degree and clustering coefficient. Transportation networks can be used as an indicator of economic activity between cities. Cities with strong economic relationship are characterized by high volume of connectivity. Our findings suggest that the topology of the analyzed transportation networks can be used to classify the countries they belong to based on their economic development.

Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems

In this paper we investigate data structures obtained by a recursive partitioning of the multi- dimensional input domain into regions of equal size. One of the best known examples of such a structure is the quadtree . It is used here as a basis for more complex data structures. We also provide multidimensional versions of the stratified tree by van Emde Boas [vEB]. We show that under the assumption that the input points have limited precision (i.e., are drawn from the integer grid of size u ) these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for dynamic approximate nearest neighbor (under insertions and deletions) and exact on-line closest pair (under insertions only) in any constant number of dimensions. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear time (optimal) algorithm for computing the expansion of a shape represented by a region quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the operation of dilation by a ball. Received January 19, 1999; revised November 4, 1999.     

Perceived density of road maps

Maps should be designed so that users can comprehend and use the information. Display decisions, such as choosing the scale at which an area is shown, depend on properties of the displayed information such as the perceived density (PD) of the information. Taking a psychophysical approach we suggest that the PD of information in a road map is related to the scale and properties of the mapped area. 54 participants rated the PD of 60 maps from different regions. We provide a simple model that predicts the PD of electronic road map displays, using the logarithm of the number of roads, the logarithm of the number of junctions and the length of the shown roads. The PD model was cross-validated using a different set of 60 maps (n = 44). The model can be used for automatically adjusting display scales and for evaluating map designs, considering the required PD to perform a map-related task.     

Optically detected magnetic resonance of thiol-capped CdTe nanocrystals

The optical properties of thiol-stabilized CdTe nanocrystals have been examined. The thiol groups -SR generate a CdS shell at the interface, leading to a CdTe/CdS core—shell structure. The present paper describes our efforts to identify the influence of the CdTe–SR interface on the optical properties of the nanocrystals, utilizing photoluminescence and optically detected magnetic resonance (ODMR) spectroscopy. The photoluminescence spectrum consists of an excitonic peak, overlapped by a broad band at lower energies. The ODMR spectrum, in the spectral regime of the broad band, showed two resonance signals. They are associated with a trapped hole at an anisotropic site of a cadmium vacancy at the Cd–SR interface and an electron in the conduction band.     

Limits to the evolution of dispersal kernels under rapid fragmentation

Adaptive evolution of dispersal strategies is one mechanism by which species can respond to rapid environmental changes. However, under rapid anthropogenic fragmentation, the evolution of dispersal may be limited, and species may be unable to adequately adapt to fragmented landscapes. Here, we develop a spatially explicit model to investigate the evolution of dispersal kernels under various combinations of fragmentation dynamics and initial conditions. We also study the consequences of modelling an evolutionary process in which dispersal phenotypes continuously and gradually shift in phenotype space in a manner corresponding to a polygenic underlying genetic architecture. With rapid fragmentation rates, we observed the emergence of long-term transient states in which dispersal strategies are not well suited to fragmented landscapes. We also show that the extent and length of these transient states depend on the pre-fragmentation dispersal strategy of the species, as well as on the rate of the fragmentation process leading to the fragmented landscape. In an increasingly fragmented world, understanding the ability of populations to adapt, and the effects that rapid fragmentation has on the evolution of dispersal, is critical for an informed assessment of species viability in the Anthropocene.     

Computing the fault tolerance of multi-agent deployment

A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i.e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i.e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment—these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities—these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.     

Using and determining location in a context-sensitive tour guide

In a study that provided unique insights into the challenges associated with developing location-based applications, the Lancaster Guide project used members of the general public to test a network-centric electronic tourist guide. We discuss two main topics. The first is our choice of positioning technology - beacons that broadcast using an IEEE 802.11 wireless network combined with user input. The second topic concerns techniques for generating custom tours for electronic city-guide systems. Guide generates these custom tours by taking into account multiple contextual triggers and user preferences. In practice, producing good tours and, indeed, assessing the quality of a tour are difficult tasks. While our analysis of techniques for producing custom tours is somewhat specific to the city-guide domain we believe that the majority of our work is relevant to location-based systems in general