### CSG Operations of Arbitrary Primitives with Interval Arithmetic and Real-Time Ray Casting

Younis Hijazi, Aaron Knoll, Mathias Schott, Andrew Kensler & Charles Hansen
We apply Knoll et al.'s algorithm [Knoll et al., "Fast ray tracing of arbitrary implicit surfaces with interval and affine arithmetic.", Comput. Graph. Forum, 28(1):2640, 2009] to interactively ray-cast constructive solid geometry (CSG) objects of arbitrary primitives represented as implicit functions. Whereas modeling globally with implicit surfaces suffers from a lack of control, implicits are well-suited for arbitrary primitives and can be combined through various operations. The conventional way to represent union and intersection with...

### Tensor Field Reconstruction Based on Eigenvector and Eigenvalue Interpolation

Ingrid Hotz, Jaya Sreevalsan-Nair, Hans Hagen & Bernd Hamann
Interpolation is an essential step in the visualization process. While most data from simulations or experiments are discrete many visualization methods are based on smooth, continuous data approximation or interpolation methods. We introduce a new interpolation method for symmetrical tensor fields given on a triangulated domain. Differently from standard tensor field interpolation, which is based on the tensor components, we use tensor invariants, eigenvectors and eigenvalues, for the interpolation. This interpolation minimizes the number of...

### Tracking Lines in Higher Order Tensor Fields

Mario Hlawitschka & Gerik Scheuermann
While tensors occur in many areas of science and engineering, little has been done to visualize tensors with order higher than two. Tensors of higher orders can be used for example to describe complex diffusion patterns in magnetic resonance imaging (MRI). Recently, we presented a method for tracking lines in higher order tensor fields that is a generalization of methods known from first order tensor fields (vector fields) and symmetric second order tensor fields. Here,...

### Pre-operative Planning and Intra-operative Guidance for Shoulder Replacement Surgery

Charl P. Botha, Peter R. Krekel, Edward R. Valstar, Paul W. De Bruin & P.M. Rozing
Shoulder joint replacement, or arthroplasty, is indicated in cases where arthritis or trauma has resulted in severe joint damage that in turn causes increased pain and decreased function. However, shoulder arthroplasty is less successful than hip and knee replacement, mostly due to the complexity of the shoulder joint and the resultant complexity of the replacement operation. In this paper we present a complete visualization-oriented pre-operative planning and intra-operative guidance approach for shoulder joint replacement. Our...

### Local and Global Illumination in the Volume Rendering Integral

Nelson Max & Min Chen
This article is intended as an update of the major survey by Max [Max, "Optical models for direct volume rendering.", IEEE Trans. on Visualization and Computer Graphics, 1(2):99108, 1995] on optical models for direct volume rendering. It provides a brief overview of the subject scope covered by [Max, "Optical models for direct volume rendering.", IEEE Trans. on Visualization and Computer Graphics, 1(2):99108, 1995], and brings recent developments, such as new shadow algorithms and refraction rendering,...

### Equilibria, Fixed Points, and Complexity Classes

Mihalis Yannakakis
Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov...

### On Geometric Spanners of Euclidean and Unit Disk Graphs

Ljubomir Perkovic & Iyad A. Kanj
We consider the problem of constructing bounded-degree planar geometric spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay subgraph is a planar geometric spanner with stretch factor $C_{delapprox 2.42$; however, its degree may not be bounded. Our first result is a very simple linear time algorithm for constructing a subgraph of the Delaunay graph with stretch factor $ho =1+2pi(kcos{frac{pi{k)^{-1$ and degree bounded by $k$, for any integer parameter $kgeq 14$....

### Distinguishing Short Quantum Computations

Bill Rosgen
Distinguishing logarithmic depth quantum circuits on mixed states is shown to be complete for $QIP$, the class of problems having quantum interactive proof systems. Circuits in this model can represent arbitrary quantum processes, and thus this result has implications for the verification of implementations of quantum algorithms. The distinguishability problem is also complete for $QIP$ on constant depth circuits containing the unbounded fan-out gate. These results are shown by reducing a $QIP$-complete problem to a...

### On the decomposition of k-valued rational relations

Jacques Sakarovitch & Rodrigo De Souza
We give a new, and hopefully more easily understandable, structural proof of the decomposition of a $k$-valued transducer into $k$ unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves...

### Preface -- 25th International Symposium on Theoretical Aspects of Computer Science

Susanne Albers & Pascal Weil
The interest in STACS has remained at a high level over the past years. The STACS 2008 call for papers led to approximately 200 submissions from 38 countries. Each was assigned to at least three program committee members. The program committee held a 2-week long electronic meeting at the end of November, to select 54 papers. As co-chairs of this committee, we would like to sincerely thank its members and the many external referees for...

### Limit complexities revisited

Laurent Bienvenu, Andrej Muchnik, Alexander Shen & Nikolay Veraschagin
The main goal of this paper is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result from (Vereshchagin, 2002) saying that $limsup_{nKS(x|n)$ (here $KS(x|n)$ is conditional (plain) Kolmogorov complexity of $x$ when $n$ is known) equals $KS^{mathbf{0'(x)$, the plain Kolmogorov complexity with $mathbf{0'$-oracle. Then we use the same argument to prove similar results for prefix complexity (and also improve results of...

### Minimizing Flow Time in the Wireless Gathering Problem

Vincenzo Bonifaci, Peter Korteweg & Alberto Marchetti-Spaccamela
We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than $Omega(m^{1/3)$ when $m$ packets have to be transmitted, unless $P = NP$. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this...

### Stackelberg Network Pricing Games

Patrick Briest, Martin Hoefer & Piotr Krysta
We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of $m$ priceable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader's prices. The leader receives as revenue the...

### Succinctness of the Complement and Intersection of Regular Expressions

Wouter Gelade & Frank Neven
We study the succinctness of the complement and intersection of regular expressions. In particular, we show that when constructing a regular expression defining the complement of a given regular expression, a double exponential size increase cannot be avoided. Similarly, when constructing a regular expression defining the intersection of a fixed and an arbitrary number of regular expressions, an exponential and double exponential size increase, respectively, can in worst-case not be avoided. All mentioned lower bounds...

### The Frobenius Problem in a Free Monoid

Jui-Yi Kao, Jeffrey Shallit & Zhi Xu
The classical Frobenius problem over ${mathbb N}$ is to compute the largest integer $g$ not representable as a non-negative integer linear combination of non-negative integers $x_1, x_2, ldots, x_k$, where $gcd(x_1, x_2, ldots, x_k) = 1$. In this paper we consider novel generalizations of the Frobenius problem to the noncommutative setting of a free monoid. Unlike the commutative case, where the bound on $g$ is quadratic, we are able to show exponential or subexponential behavior...

### Ultimate Traces of Cellular Automata

Julien Cervelle, Enrico Formenti & Pierre Guillon
A cellular automaton (CA) is a parallel synchronous computing model, which consists in a juxtaposition of finite automata (cells) whose state evolves according to that of their neighbors. Its trace is the set of infinite words representing the sequence of states taken by some particular cell. In this paper we study the ultimate trace of CA and partial CA (a CA restricted to a particular subshift). The ultimate trace is the trace observed after a...

### On Iterated Dominance, Matrix Elimination, and Matched Paths

Felix Brandt, Felix Fischer & Markus Holzer
We study computational problems arising from the iterated removal of weakly dominated actions in anonymous games. Our main result shows that it is NP-complete to decide whether an anonymous game with three actions can be solved via iterated weak dominance. The two-action case can be reformulated as a natural elimination problem on a matrix, the complexity of which turns out to be surprisingly difficult to characterize and ultimately remains open. We however establish connections to...

• 2010
155,679

• Text
155,679

#### Affiliations

• Helmholtz Centre Potsdam - GFZ German Research Centre for Geosciences
20
• University of Copenhagen
6
• University of Milano-Bicocca
4
• Charles University
4
• University of Insubria
2
• University of Aberdeen
2
• University of Clermont Auvergne
2
• Aarhus University
2
• Polish Academy of Sciences
2
• National Academy of Sciences of the Republic of Kyrgyzstan
2