Visualization and Analysis‐Oriented Reconstruction of Material Interfaces

Reconstructing boundaries along material interfaces from volume fractions is a difficult problem, especially because the under‐resolved nature of the input data allows for many correct interpretations. Worse, algorithms widely accepted as appropriate for simulation are inappropriate for visualization. In this paper, we describe a new algorithm that is specifically intended for reconstructing material interfaces for visualization and analysis requirements. The algorithm performs well with respect to memory footprint and execution time, has desirable properties in various accuracy metrics, and also produces smooth surfaces with few artifacts, even when faced with more than two materials per cell.     

Adopt,adapt, abandon: Understanding why some young adults start,and then stop,using instant messaging

Instant messaging (IM) has become a popular and important mode of staying in touch for teens and young adults. It allows for easy, frequent and lightweight interaction that contributes to building and sustaining friendships, as well as coordinating social activities. Despite the initial appeal of IM, however, some have found it too distracting and have changed their usage or abandoned it. I interviewed 21 former users of IM about their adoption, usage and eventual abandonment of the technology. Results show that participants were initially attracted to features of IM that enabled them to maximize their use of leisure time via easy and frequent interaction with their friends, but that, in a different usage context, these same features became distracting and annoying. Participants adapted their behavior to avoid these drawbacks, but IM did not support these adaptations effectively. In particular, IM did not allow for control over interruptions, which became more important as their contact lists grew and social time became scarce; and they ultimately abandoned the technology. These results point to a need for understanding use beyond adoption, and a theoretical and practical focus on understanding the adaptation and changing utility that accompany long-term usage of technologies.     

Indoor robot gardening: design and implementation

This paper describes the architecture and implementation of a distributed autonomous gardening system with applications in urban/indoor precision agriculture. The garden is a mesh network of robots and plants. The gardening robots are mobile manipulators with an eye-in-hand camera. They are capable of locating plants in the garden, watering them, and locating and grasping fruit. The plants are potted cherry tomatoes enhanced with sensors and computation to monitor their well-being (e.g. soil humidity, state of fruits) and with networking to communicate servicing requests to the robots. By embedding sensing, computation, and communication into the pots, task allocation in the system is de-centrally coordinated, which makes the system scalable and robust against the failure of a centralized agent. We describe the architecture of this system and present experimental results for navigation, object recognition, and manipulation as well as challenges that lie ahead toward autonomous precision agriculture with multi-robot teams.     

Towards capacity and profit optimization of video-on-demand services in a peer-assisted IPTV platform

This paper studies the conditions under which peer-to-peer (P2P) technology may be beneficial in providing IPTV services over typical network architectures. It has three major contributions. First, we contrast two network models used to study the performance of such a system: a commonly used logical “Internet as a cloud” model and a “physical” model that reflects the characteristics of the underlying network. Specifically, we show that the cloud model overlooks important architectural aspects of the network and may drastically overstate the benefits of P2P technology. Second, we propose an algorithm called Zebra that pre-stripes content across multiple peers during idle hours to speed up P2P content delivery in an IPTV environment with limited upload bandwidth. We also perform simulations to measure Zebra’s effectiveness at reducing load on the content server during peak hours. Third, we provide a cost-benefit analysis of P2P video content delivery, focusing on the profit trade-offs for different pricing/incentive models rather than purely on capacity maximization. In particular, we find that under high volume of video demand, a P2P built-in incentive model performs better than any other model, while the conventional no-P2P model generates more profits when the request rate is low. The flat-reward model generally falls in between the usage-based model and the built-in model in terms of profitability except for low request rates. We also find that built-in and flat-reward models are more profitable than the usage-based model for a wide range of subscriber community sizes. Funding for J. Rahe’s research has been provided by AT&T Labs, the State of California under the MICR Oprogram, and by the Toshiba Corporation. Zhen Xiao is partially supported by China MOST project (2006BAH02A10).     

Property specifications for workflow modelling

Previously we provided two formal behavioural semantics for the Business Process Modelling Notation (BPMN) in the process algebra CSP. By exploiting CSP’s refinement orderings, developers may formally compare their BPMN models. However, BPMN is not a specification language, and it is difficult and sometimes impossible to use it to construct behavioural properties against which other BPMN models may be verified. This paper considers a pattern-based approach to expressing behavioural properties. We describe a property specification language PL for capturing a generalisation of Dwyer et al.’s Property Specification Patterns, and present a translation from PL into a bounded, positive fragment of linear temporal logic, which can then be automatically translated into CSP for simple refinement checking. We present a detailed example studying the behavioural properties of an airline ticket reservation business process. Using the same example we also describe some recent results on expressing behavioural compatibility within our semantic models. These results lead to a compositional approach for ensuring deadlock freedom of interacting business processes.     

Linear-Time Recognition of Helly Circular-Arc Models and Graphs

A circular-arc model ℳ is a circle C together with a collection A\mathcal{A} of arcs of C. If A\mathcal{A} satisfies the Helly Property then ℳ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n ³). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound.     

Algorithms for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph which has a homogeneous set. In 2001 Tang et al. published an all-fast algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset thereafter at the former determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic algorithms which have it established at We give as well two even faster randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.