Skeleton computation of orthogonal polyhedra

Skeletons are powerful geometric abstractions that provide useful representations for a number of geometric operations. The straight skeleton has a lower combinatorial complexity compared with the medial axis. Moreover, while the medial axis of a polyhedron is composed of quadric surfaces the straight skeleton just consist of planar faces. Although there exist several methods to compute the straight skeleton of a polygon, the straight skeleton of polyhedra has been paid much less attention. We require to compute the skeleton of very large datasets storing orthogonal polyhedra. Furthermore, we need to treat geometric degeneracies that usually arise when dealing with orthogonal polyhedra. We present a new approach so as to robustly compute the straight skeleton of orthogonal polyhedra. We follow a geometric technique that works directly with the boundary of an orthogonal polyhedron. Our approach is output sensitive with respect to the number of vertices of the skeleton and solves geometric degeneracies. Unlike the existing straight skeleton algorithms that shrink the object boundary to obtain the skeleton, our algorithm relies on the plane sweep paradigm. The resulting skeleton is only composed of axis‐aligned and 45° rotated planar faces and edges.     

A model of cerebral cortex formation during fetal development using reaction-diffusion-convection equations with Turing space parameters

The cerebral cortex is a gray lamina formed by bodies of neurons covering the cerebral hemispheres, varying in thickness from 1.25 mm in the occipital lobe to 4 mm in the anterior lobe. The brain's surface is about 30 times greater that of the skull because of its many folds; such folds form the gyri, sulci and fissures and mark out areas having specific functions, divided into five lobes. Convolution formation may vary between individuals and is an important feature of brain formation; such patterns can be mathematically represented as Turing patterns. This article describes how a phenomenological model was developed by describing the formation pattern for the gyri occurring in the cerebral cortex by reaction diffusion equations with Turing space parameters. Numerical examples for simplified geometries of a brain were solved to study pattern formation. The finite element method was used for the numerical solution, in conjunction with the Newton–Raphson method. The numerical examples showed that the model can represent cerebral cortex fold formation and reproduce pathologies related to gyri formation, such as polymicrogyria and lissencephaly.     

Multi‐agent system for knowledge‐based event recognition and composition

This work presents a multi‐agent system for knowledge‐based high‐level event composition, which interprets activities, behaviour and situations semantically in a scenario with multi‐sensory monitoring. A perception agent (plurisensory agent and visual agent)‐based structure is presented. The agents process the sensor information and identify (agent decision system) significant changes in the monitored signals, which they send as simple events to the composition agent that searches for and identifies pre‐defined patterns as higher‐level semantic composed events. The structure has a methodology and a set of tools that facilitate its development and application to different fields without having to start from scratch. This creates an environment to develop knowledge‐based systems generally for event composition. The application task of our work is surveillance, and event composition/inference examples are shown which characterize an alarming situation in the scene and resolve identification and tracking problems of people in the scenario being monitored.     

MetaMol: high-quality visualization of molecular skin surface

Modeling and visualizing molecular surfaces is an important and challenging task in bioinformatics. Such surfaces play an essential role in better understanding the chemical and physical properties of molecules. However, constructing and displaying molecular surfaces requires complex algorithms. In this article we introduce MetaMol, a new program that generates high-quality images in interactive time. In contrast with existing software that discretizes the surface with triangles or grids, our program is based on a GPU accelerated ray-casting algorithm that directly uses the piecewise-defined algebraic equation of the molecular skin surface. As a result, both better performances and higher quality are obtained.     

Black-Box Correctness Tests for Basic Parallel Data Structures

Operations on basic data structures such as queues, priority queues, stacks, and counters can dominate the execution time of a parallel program due to both their frequency and their coordination and contention overheads. There are considerable performance payoffs in developing highly optimized, asynchronous, distributed, cache-conscious, parallel implementations of such data structures. Such implementations may employ a variety of tricks to reduce latencies and avoid serial bottlenecks, as long as the semantics of the data structure are preserved. The complexity of the implementation and the difficulty in reasoning about asynchronous systems increases concerns regarding possible bugs in the implementation. In this paper we consider postmortem, black-box procedures for testing whether a parallel data structure behaved correctly. We present the first systematic study of algorithms and hardness results for such testing procedures, focusing on queues, priority queues, stacks, and counters, under various important scenarios. Our results demonstrate the importance of selecting test data such that distinct values are inserted into the data structure (as appropriate). In such cases we present an O(n) time algorithm for testing linearizable queues, an O(n log n) time algorithm for testing linearizable priority queues, and an O( np ² ) time algorithm for testing sequentially consistent queues, where n is the number of data structure operations and p is the number of processors. In contrast, we show that testing such data structures for executions with arbitrary input values is NP-complete. Our results also help clarify the thresholds between scenarios that admit polynomial time solutions and those that are NP-complete. Our algorithms are the first nontrivial algorithms for these problems.     

Multimodal support to group dynamics

The complexity of group dynamics occurring in small group interactions often hinders the performance of teams. The availability of rich multimodal information about what is going on during the meeting makes it possible to explore the possibility of providing support to dysfunctional teams from facilitation to training sessions addressing both the individuals and the group as a whole. A necessary step in this direction is that of capturing and understanding group dynamics. In this paper, we discuss a particular scenario, in which meeting participants receive multimedia feedback on their relational behaviour, as a first step towards increasing self-awareness. We describe the background and the motivation for a coding scheme for annotating meeting recordings partially inspired by the Bales’ Interaction Process Analysis. This coding scheme was aimed at identifying suitable observable behavioural sequences. The study is complemented with an experimental investigation on the acceptability of such a service.

---

Dynamic voltage scaling under EDF revisited

Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.

QDENSITY—A Mathematica Quantum Computer simulation

This Mathematica 5.2 package¹ is a simulation of a Quantum Computer. The program provides a modular, instructive approach for generating the basic elements that make up a quantum circuit. The main emphasis is on using the density matrix, although an approach using state vectors is also implemented in the package. The package commands are defined in Qdensity.m which contains the tools needed in quantum circuits, e.g., multiqubit kets, projectors, gates, etc. Selected examples of the basic commands are presented here and a tutorial notebook, Tutorial.nb is provided with the package (available on our website) that serves as a full guide to the package. Finally, application is made to a variety of relevant cases, including Teleportation, Quantum Fourier transform, Grover's search and Shor's algorithm, in separate notebooks: QFT.nb, Teleportation.nb, Grover.nb and Shor.nb where each algorithm is explained in detail. Finally, two examples of the construction and manipulation of cluster states, which are part of “one way computing” ideas, are included as an additional tool in the notebook Cluster.nb. A Mathematica palette containing most commands in QDENSITY is also included: QDENSpalette.nb.

Program summary

Title of program: QDENSITYCatalogue identifier: ADXH_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXH_v1_0Program available from: CPC Program Library, Queen's University of Belfast, N. IrelandOperating systems: Any which supports Mathematica; tested under Microsoft Windows XP, Macintosh OS X, and Linux FC4Programming language used: Mathematica 5.2No. of bytes in distributed program, including test data, etc.: 180 581No. of lines in distributed program, including test data, etc.: 19 382Distribution format: tar.gzMethod of solution: A Mathematica package is provided which contains commands to create and analyze quantum circuits. Several Mathematica notebooks containing relevant examples: Teleportation, Shor's Algorithm and Grover's search are explained in detail. A tutorial, Tutorial.nb is also enclosed.     

Software assessment using metrics: A comparison across large C++ and Java systems

This paper presents an assessment method to evaluate the quality of object oriented software systems. The assessment method is based on source code abstraction, object–oriented metrics and graphical representation. The metrics used and the underlying model representing the software are presented. The assessment method experiment is part of an industrial research effort with the Bell Canada Quality Engineering and Research Group. It helps evaluators assess the quality and risks associated with software by identifying code fragments presenting unusual characteristics. The assessment method evaluates object–oriented software systems at three levels of granularity: system level, class level and method level. One large C++ and eight Java software systems, for a total of over one million lines of code, are presented as case studies. A critical analysis of the results is presented comparing the systems and the two languages.