2020-10-25T20:49:39Zhttp://edoc.mpg.de/ac_p_oai.ploai:edoc.mpg.de:2017822012-09-1987:933
Towards cellular function through metabolite screening
Talwar, Priti
Lengauer, Thomas
Wittmann, Christoph
Mangadu, Vidya
Heinzle, Elmar
Cambridge Healthtech Institute
2003
Conference-Paper
http://edoc.mpg.de/201782
Proceedings of the 3rd Annual Conference on Metabolic Profiling: Pathways in Discovery, Cambridge Healthtech Institute, 7-7 (2003)
en
oai:edoc.mpg.de:2017852012-09-1987:931
A theoretical and experimental study on the construction of suffix arrays in external memory
Crauser, Andreas
Ferragina, Paolo
The construction of full-text indexes on very large text collections
is nowadays a hot problem. The suffix array [Manber-Myers,~1993] is
one of the most attractive full-text indexing data structures due to
its simplicity, space efficiency and powerful/fast search operations
supported. In this paper we analyze, both theoretically and
experimentally, the I/O-complexity and the working space of six
algorithms for constructing large suffix arrays. Three of them are
the state-of-the-art, the other three algorithms are our new
proposals. We perform a set of experiments based on three different
data sets (English texts, Amino-acid sequences and random texts) and
give a precise hierarchy of these algorithms according to their
working-space vs. construction-time tradeoff. Given the current
trends in model design~\cite{Farach-et-al,Vitter} and disk
technology~\cite{quantum,Ruemmler-Wilkes}, we will pose particular
attention to differentiate between ``random'' and ``contiguous''
disk accesses, in order to reasonably explain some practical
I/O-phenomena which are related to the experimental behavior of
these algorithms and that would be otherwise meaningless in the
light of other simpler external-memory models.
At the best of our knowledge, this is the first study which provides
a wide spectrum of possible approaches to the construction of suffix
arrays in external memory, and thus it should be helpful to anyone
who is interested in building full-text indexes on very large text
collections.
Finally, we conclude our paper by addressing two other issues. The
former concerns with the problem of building word-indexes; we show
that our results can be successfully applied to this case too,
without any loss in efficiency and without compromising the
simplicity of programming so to achieve a uniform, simple and
efficient approach to both the two indexing models. The latter issue
is related to the intriguing and apparently counterintuitive
``contradiction'' between the effective practical performance of the
well-known BaezaYates-Gonnet-Snider's algorithm~\cite{book-info},
verified in our experiments, and its unappealing (i.e., cubic)
worst-case behavior. We devise a new external-memory algorithm that
follows the basic philosophy underlying that algorithm but in a
significantly different manner, thus resulting in a novel approach
which combines good worst-case bounds with efficient practical
performance.
2002
Article
http://edoc.mpg.de/201785
urn:ISSN:0178-4617
Algorithmica, v.32, 1-35 (2002)
en
oai:edoc.mpg.de:2017872012-09-1987:933
Bioinformatikmethoden für die Optimierung antiviraler Kombinationstherapien
Beerenwinkel, Niko
Däumer, Martin
Hoffmann, Daniel
Kaiser, Rolf
Selbig, Joachim
Lengauer, Thomas
K. G. Saur Verlag
2003
InBook
http://edoc.mpg.de/201787
urn:ISBN:3-598-24930-6
Max-Planck-Gesellschaft: MPG Jahrbuch 2003, 481-486 (2003)
de
oai:edoc.mpg.de:2017882012-09-1987:931
Heuristics for Semi-External Depth First Search on Directed Graphs
Sibeyn, Jop F.
Abello, James
Meyer, Ulrich
Computing the strong components of a directed graph is an essential
operation for a basic structural analysis of it. This problem can
be solved by twice running a depth-first search (DFS).
In an external setting, in which all data can no longer be stored in
the main memory, the DFS problem is unsolved so far. Assuming that
node-related data can be stored internally, semi-external computing
does not make the problem substantially easier. Considering the
definite need to analyze very large graphs, we have developed a set
of heuristics which together allow the performance of semi-external DFS for
directed graphs in practice. The heuristics have been applied to
graphs with very different graph properties, including ``web graphs''
as described in the most recent literature and some call graphs from
ATT. Depending on the graph structure, the program is between 10 and
200 times faster than the best alternative, a factor that will
further increase with future technological developments.
ACM
2002
Conference-Paper
http://edoc.mpg.de/201788
urn:ISBN:1-58113-529-7
SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, 282-292 (2002)
en
oai:edoc.mpg.de:2017892012-09-1987:931
Exact geometric computation
Mehlhorn, Kurt
Lipitakis, Elias A.
LEA
2002
Conference-Paper
http://edoc.mpg.de/201789
urn:ISBN:960-85176-9-9
HERCMA 2001 : proceedings of the 5th Hellenic-European Conference on Computer Mathematics and its Applications (HERCMA-01), LEA, 87-87 (2002)
en
oai:edoc.mpg.de:2017902012-09-1987:933
Molecular dynamics simulations of photoactive yellow protein (PYP) in three states of its photocycle: a comparison with X-ray and NMR data and analysis of the effects of Glu46 deprotonation and mutation
Antes, Iris
Thiel, Walter
Gunsteren van, Wilfred F.
2002
Article
http://edoc.mpg.de/201790
urn:ISSN:0175-7571
European Biophysics Jounal, v.31, 504-520 (2002)
en
oai:edoc.mpg.de:2017922012-09-1987:930
Classification and Focused Crawling for Semistructured Data
Theobald, Martin
Schenkel, Ralf
Weikum, Gerhard
Blanken, Henk
Grabs, Torsten
Schek, Hans-Jörg
Schenkel, Ralf
Weikum, Gerhard
Springer
2003
InBook
http://edoc.mpg.de/201792
urn:ISBN:3-540-40768-5
Intelligent Search on XML Data : Applications, Languages, Models, Implementations, and Benchmarks, 145-157 (2003)
en
oai:edoc.mpg.de:2017932012-09-1987:931
External-Memory Breadth-First Search with Sublinear I/O
Mehlhorn, Kurt
Meyer, Ulrich
Möhring, Rolf
Raman, Rajeev
Breadth-first search (BFS) is a basic graph exploration technique.
We give the first external-memory algorithm for sparse
undirected graphs with sublinear I/O. The best
previous algorithm requires O( n + sort(n+m) ) I/Os
on a graph with n nodes and m edges and a machine with
main-memory of size M, D parallel disks, and block size B.
We present two versions of a new algorithm which requires only
O( sqrt( n/m * (n+m)/(D*B) ) * log_{M/B} (n/B) + sort(n+m)) I/Os
(expected or worst-case, respectively).
Hence, for m = O(n), they improve upon the I/O-performance
of the best previous algorithm by nearly a factor of sqrt(D*B).
Our approach is fairly simple and we conjecture at least the
randomized version to be practical.
Springer
2002
Conference-Paper
http://edoc.mpg.de/201793
urn:ISBN:3-540-44180-8
Algorithms - ESA 2002 : 10th Annual European Symposium, Springer, 723-735 (2002)
en
oai:edoc.mpg.de:2017942012-09-1987:934
Dual/Primal Mesh Optimization for Polygonized Implicit Surfaces
Ohtake, Yutaka
Belyaev, Alexander
Lee, Kunwoo
Patrikalakis, Nicho M.
A new method for improving polygonizations of implicit surfaces with
sharp features is proposed. The method is based on the observation
that, given an implicit surface with sharp features, a triangle
mesh whose triangles are tangent to the implicit surface at certain
inner triangle points gives a better approximation of the implicit
surface than the standard marching cubes mesh \cite{Lorensen}
(in our experiments we use VTK marching cubes \cite{VTK}).
First, given an initial triangle mesh, its dual mesh composed of
the triangle centroids is considered. Then the dual mesh is modified such
that its vertices are placed on the implicit surface and the mesh
dual to the modified dual mesh is considered.
Finally the vertex positions of that ``double dual'' mesh are optimized
by minimizing a quadratic energy measuring a deviation of the mesh
normals from the implicit surface normals computed at the vertices
of the modified dual mesh. In order to achieve an accurate approximation
of fine surface features, these basic steps are combined with adaptive
mesh subdivision and curvature-weighted vertex resampling. The proposed
method outperforms approaches based on the mesh evolution paradigm
in speed and accuracy.
ACM
2002
Conference-Paper
http://edoc.mpg.de/201794
urn:ISBN:1-58113-506-8
Seventh ACM Symposium on Solid Modeling and Applications (SM-02), ACM, 171-178 (2002)
en
oai:edoc.mpg.de:2017952012-09-1987:934
A Framework for Dynamic Connectivity Meshes
Vorsatz, Jens
Seidel, Hans-Peter
Reiners, D.
Implementing algorithms that are based on dynamic triangle meshes
often requires updating internal data-structures as soon as the
connectivity of the mesh changes. The design of a class hierarchy
that is able to deal with such changes is particularly challenging if the
system reaches a certain complexity.
The paper proposes a software design that enables the users to
efficiently implement algorithms that can handle these dynamic
changes while still maintaining a certain encapsulation of the
single components.
Our design is based on a callback mechanism. A client can register at some {\tt
Info}-object and gets informed whenever a change of the connectivity occurs.
This way the client is able to keep internal data up-to-date. Our framework
enables us to write small client classes that cover just a small dedicated
aspect of necessary updates related to the changing connectivity. These small
components can be combined to more complex modules and can often easily be
reused. Moreover, we do not have to store related 'dynamic data' in one central
place, e.g. the mesh, which could lead to a significant memory overhead if an
application uses some modules just for a short time.
We have used and tested this class design extensively for
implementing 'Dynamic Connectivity Meshes and
Applications~\cite{Vorsatz:2003:DRA}'. Additionally, as a
feasibility study, we have implemented and integrated our concept in the
\OM-framework.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201795
OpenSG Symposium 2003, ACM, 49-55 (2003)
en
oai:edoc.mpg.de:2017962012-09-1987:931
Minimum Cost Flows Over Time without Intermediate Storage
Fleischer, Lisa
Skutella, Martin
Flows over time (also called dynamic flows)
generalize standard network flows by introducing
an element of time. They naturally model problems where
travel and transmission are not instantaneous. Solving these problems
raises issues that do not arise in standard network flows.
One issue is the question of storage of flow at intermediate nodes.
In most applications
(such as, e.g., traffic routing, evacuation planning,
telecommunications etc.), intermediate storage is limited, undesired,
or prohibited.
The minimum cost flow over time problem is NP-hard. In this paper we
1)~prove that the minimum cost flow over time never requires storage;
2)~provide the first approximation scheme for minimum cost flows over
time that does not require storage; 3)~provide the first approximation
scheme for minimum cost flows over time that meets hard cost
constraints, while approximating only makespan.
Our approach is based on a condensed variant of time-expanded
networks. It also yields fast approximation schemes with simple
solutions for the quickest multicommodity flow problem.
Finally, using completely different techniques, we describe a very
simple capacity scaling FPAS for the minimum cost flow over time
problem when costs are proportional to transit times.
The algorithm builds upon our observation about the
structure of optimal solutions to this problem:
they are universally quickest flows. Again, the FPAS
does not use intermediate node storage.
In contrast to the preceding algorithms that use a
time-expanded network, this FPAS runs directly on the original
network.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201796
urn:ISBN:0-89871-538-5
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 66-75 (2003)
en
oai:edoc.mpg.de:2017982012-09-1987:934
Precomputed Radiance Transfer for Real-Time Rendering in Dynamic, Low-Frequency Lighting Environments
Sloan, Peter-Pike
Kautz, Jan
Snyder, John
Fiume, Eugene
We present a new, real-time method for rendering diffuse and glossy
objects in low-frequency lighting environments that cap-tures soft
shadows, interreflections, and caustics. As a preprocess, a novel
global transport simulator creates functions over the object s surface
representing transfer of arbitrary, low-frequency incident lighting
into transferred radiance which includes global effects like shadows
and interreflections from the object onto itself. At run-time, these
transfer functions are applied to actual incident lighting. Dynamic,
local lighting is handled by sampling it close to the object every
frame; the object can also be rigidly rotated with respect to the
lighting and vice versa. Lighting and transfer functions are
represented using low-order spherical harmonics. This avoids aliasing
and evaluates efficiently on graphics hardware by reducing the shading
integral to a dot product of 9 to 25 element vectors for diffuse
receivers. Glossy objects are handled using matrices rather than
vectors. We further introduce functions for radiance transfer from a
dynamic lighting environment through a preprocessed object to
neighboring points in space. These allow soft shadows and caustics
from rigidly moving objects to be cast onto arbitrary, dynamic
receivers. We demonstrate real-time global lighting effects with this
approach.
ACM
2002
Conference-Paper
http://edoc.mpg.de/201798
urn:ISBN:1-58113-521-1
Proceedings of ACM SIGGRAPH 2002 (SIGGRAPH-02), ACM, 527-536 (2002)
en
oai:edoc.mpg.de:2017992012-09-1987:934
Matrix Radiance Transfer
Lehtinen, Jaakko
Kautz, Jan
Spencer, Stephen N.
Precomputed Radiance Transfer allows interactive rendering of objects
illuminated by low-frequency environment maps, including self-shadowing and
interreflections. The expensive integration of incident lighting is partially
precomputed and stored as matrices.
Incorporating anisotropic, glossy BRDFs into precomputed radiance
transfer has been previously shown to be possible, but none of the
previous methods offer real-time performance. We propose a new
method, \textit{matrix radiance transfer}, which significantly
speeds up exit radiance computation and allows anisotropic BRDFs.
We generalize the previous radiance transfer methods to work with a
matrix representation of the BRDF and optimize exit radiance
computation by expressing the exit radiance in a new, directionally
locally supported basis set instead of the spherical harmonics. To
determine exit radiance, our method performs four dot products per
vertex in contrast to previous methods, where a full matrix-vector
multiply is required. Image quality can be controlled by adapting
the number of basis functions. We compress our radiance transfer
matrices through principal component analysis (PCA). We show that it
is possible to render directly from the PCA representation, which
also enables the user to trade interactively between quality and
speed.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201799
urn:ISBN:1-58113-645-5
ACM SIGGRAPH 2003 Symposium on Interactive 3D Graphics, ACM, 59-64 (2003)
en
oai:edoc.mpg.de:2018002012-09-1987:934
Efficient Light Transport Using Precomputed Visibility
Daubert, Katja
Heidrich, Wolfgang
Kautz, Jan
Dischler, Jean-Michel
Seidel, Hans-Peter
Visibility computations are the most time-consuming part of
global illumination algorithms. The cost is amplified by the
fact that quite often identical or similar information is
recomputed multiple times. In particular this is the case when
multiple images of the same scene are to be generated under
varying lighting conditions and/or viewpoints. But even for a
single image with static illumination, the computations could be
accelerated by reusing visibility information for many different
light paths.
In this paper we describe a general method of precomputing,
storing, and reusing visibility information for light transport
in a number of different types of scenes. In particular, we
consider general parametric surfaces, triangle meshes without a
global parameterization, and participating media.
We also reorder the light transport in such a way that the
visibility information is accessed in structured memory access
patterns. This yields a method that is well suited for SIMD-style
parallelization of the light transport, and can efficiently be
implemented both in software and using graphics hardware. We
finally demonstrate applications of the method to highly
efficient precomputation of BRDFs, bidirectional texture
functions, light fields, as well as near-interactive volume
lighting.
2003
Article
http://edoc.mpg.de/201800
IEEE Computer Graphics and Applications, v.23, 28-37 (2003)
en
oai:edoc.mpg.de:2018012012-09-1987:931
Better Filtering with Gapped q-Grams
Burkhardt, Stefan
Kärkkäinen, Juha
A popular and well-studied class of filters for approximate string
matching compares substrings of length $q$, \emph{the $q$-grams}, in
the pattern and the text to identify text areas that contain potential
matches. A generalization of the method that uses {\em gapped}
$q$-grams instead of contiguous substrings is mentioned a few times in
literature but has never been analyzed in any depth. In this paper,
we report the first results of a study on gapped $q$-grams. We show
that gapped $q$-grams can provide orders of magnitude faster and/or
more efficient filtering than contiguous $q$-grams. To achieve these
results the arrangement of the gaps in the $q$-gram and a filter
parameter called \emph{threshold} have to be optimized. Both of these
tasks are nontrivial combinatorial optimization problems for which we
present efficient solutions. We concentrate on the $k$~mismatches
problem, i.e, approximate string matching with the Hamming distance.
2003
Article
http://edoc.mpg.de/201801
urn:ISSN:0169-2968
Fundamenta Informaticae, v.56, 51-70 (2003)
en
oai:edoc.mpg.de:2018022012-09-1987:934
Advanced Global Illumination
Dutré, Philip
Bekaert, Philippe
Bala, Kavita
A K Peters
2003
Book
http://edoc.mpg.de/201802
en
oai:edoc.mpg.de:2018032012-09-1987:934
Improved Hardware-Accelerated Visual Hull Rendering
Li, Ming
Magnor, Marcus
Seidel, Hans-Peter
Ertl, Thomas
Girod, Bernd
Greiner, Günther
Niemann, Heinrich
Seidel, Hans-Peter
Steinbach, Eckehard
Westermann, Rüdiger
The visual hull is an efficient shape approximation for the purpose of
reconstructing and visualizing dynamic objects. Recently, rapid progress in
graphics hardware development has made it possible to render visual hulls from
a set of silhouette images in real-time.
In this paper we present several new algorithms to improve the generality and
quality of hardware-accelerated visual hull rendering. First, a multi-pass
approach employs texture objects and the stencil buffer to enable the visual
hull rendering algorithm to deal with arbitrary numbers of input images.
Secondly, flexible programmability of state-of-the-art graphics hardware is
exploited to achieve smooth transitions between textures from different
reference views projected onto visual hulls. In addition, visibility problems
with projective texture mapping are solved by using the shadow mapping
technique. We test our rendering algorithms on various off-the-shelf graphics
cards and achieve real-time frame rates.
Akademische Verlagsgesellschaft Aka
2003
Conference-Paper
http://edoc.mpg.de/201803
urn:ISBN:3-89838-048-3
Vision, Modeling and Visualization 2003 (VMV-03) : proceedings, Akademische Verlagsgesellschaft Aka, 151-158 (2003)
en
oai:edoc.mpg.de:2018042010-12-0387:937
Improved Hardware-Accelerated Visual Hull Rendering
Li, Ming
Magnor, Marcus
Seidel, Hans-Peter
Ertl, Thomas
Girod, Bernd
Greiner, Günther
Niemann, Heinrich
Seidel, Hans-Peter
Steinbach, Eckehard
Westermann, Rüdiger
The visual hull is an efficient shape approximation for the purpose of
reconstructing and visualizing dynamic objects. Recently, rapid progress in
graphics hardware development has made it possible to render visual hulls from
a set of silhouette images in real-time.
In this paper we present several new algorithms to improve the generality and
quality of hardware-accelerated visual hull rendering. First, a multi-pass
approach employs texture objects and the stencil buffer to enable the visual
hull rendering algorithm to deal with arbitrary numbers of input images.
Secondly, flexible programmability of state-of-the-art graphics hardware is
exploited to achieve smooth transitions between textures from different
reference views projected onto visual hulls. In addition, visibility problems
with projective texture mapping are solved by using the shadow mapping
technique. We test our rendering algorithms on various off-the-shelf graphics
cards and achieve real-time frame rates.
Akademische Verlagsgesellschaft Aka
2003
Conference-Paper
http://edoc.mpg.de/201804
urn:ISBN:3-89838-048-3
Vision, Modeling and Visualization 2003 (VMV-03) : proceedings, Akademische Verlagsgesellschaft Aka, 151-158 (2003)
en
oai:edoc.mpg.de:2018052010-12-0387:937
Interactive Rendering of Translucent Objects
Lensch, Hendrik
Goesele, Michael
Bekaert, Philippe
Kautz, Jan
Magnor, Marcus
Lang, Jochen
Seidel, Hans-Peter
This paper presents a rendering method for translucent objects, in which
viewpoint and illumination can be
modified at interactive rates. In a preprocessing step, the impulse response to
incoming light impinging at each
surface point is computed and stored in two different ways: The local effect on
close-by surface points is modeled
as a per-texel filter kernel that is applied to a texture map representing the
incident illumination. The global
response (i.e. light shining through the object) is stored as vertex-to-vertex
throughput factors for the triangle
mesh of the object. During rendering, the illumination map for the object is
computed according to the current
lighting situation and then filtered by the precomputed kernels. The
illumination map is also used to derive the
incident illumination on the vertices which is distributed via the
vertex-to-vertex throughput factors to the other
vertices. The final image is obtained by combining the local and global
response. We demonstrate the performance
of our method for several models.
2003
Article
http://edoc.mpg.de/201805
urn:ISSN:0167-7055
Computer Graphics Forum, v.22, 195-205 (2003)
en
oai:edoc.mpg.de:2018062012-09-1987:931
Algorithms for Memory Hierarchies
Meyer, Ulrich
Sanders, Peter
Sibeyn, Jop F.
Springer
2003
Book
http://edoc.mpg.de/201806
urn:ISBN:3-540-00883-7
en
oai:edoc.mpg.de:2018102010-12-0287:932
Citius altius fortius: Lessons learned from the Theorem Prover WALDMEISTER
Hillenbrand, Thomas
Dahn, Ingo
Vigneron, Laurent
In the last years, the development of automated theorem
provers has been advancing in a so to speak Olympic spirit,
following the motto "faster, higher, stronger"; and the
{Waldmeister} system has been a part of that endeavour. We
will survey the concepts underlying this prover, which
implements Knuth-Bendix completion in its unfailing variant.
The system architecture is based on a strict separation of
active and passive facts, and is realized via specifically
tailored representations for each of the central data
structures: indexing for the active facts, set-based
compression for the passive facts, successor sets for the
conjectures. In order to cope with large search spaces,
specialized redundancy criteria are employed, and the
empirically gained control knowledge is integrated to ease
the use of the system. We conclude with a discussion of
strengths and weaknesses, and a view of future prospects.
Elsevier
2003
Conference-Paper
http://edoc.mpg.de/201810
Proceedings of the 4th International Workshop on First Order Theorem Proving, FTP'03, Elsevier, 1-13 (2003)
en
oai:edoc.mpg.de:2018112012-09-1987:931
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
Becchetti, Luca
Leonardi, Stefano
Marchetti-Spaccamela, Alberto
Schäfer, Guido
Vredeveld, Tjark
In this paper we introduce the notion of smoothed competitive analysis of
online algorithms. Smoothed analysis has been proposed by Spielman and Teng
\cite{ST01} to explain the behaviour of algorithms that work well in practice
while performing very poorly from a worst case analysis point of view. We
apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to
minimize the total flow time on a sequence of jobs released over time when the
processing time of a job is only known at time of completion.
The initial processing times are integers in the range $[1,2^K]$. We use a
partial bit randomization model, where the initial processing times are
smoothened by changing the $k$ least significant bits under a quite general
class of probability distributions. We show that MLF admits a smoothed
competitive ratio of $O((2^k/\sigma)^3 + (2^k/\sigma)^2 2^{K-k})$, where
$\sigma$ denotes the standard deviation of the distribution. In particular, we
obtain a competitive ratio of $O(2^{K-k})$ if $\sigma = \Theta(2^k)$. We also
prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is
run on processing times smoothened according to the partial bit randomization
model. For various other smoothening models, including the additive symmetric
smoothening model used by Spielman and Teng \cite{ST01}, we give a higher
lower bound of $\Omega(2^K)$.
A direct consequence of our result is also the first average case analysis of
MLF. We show a constant expected ratio of the total flow time of MLF to the
optimum under several distributions including the uniform distribution.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201811
44th Annual Symposium on Foundations of Computer Science (FOCS-03), IEEE, 462-471 (2003)
en
oai:edoc.mpg.de:2018122010-12-0287:932
A Principle for Incorporating Axioms into the First-Order Translation of Modal Formulae
Schmidt, Renate A.
Hustadt, Ullrich
Baader, Franz
In this paper we present a translation principle, called the
\emph{axiomatic translation}, for reducing propositional modal logics
with background theories, including
triangular properties such as transitivity, Euclideanness and
functionality, to decidable logics.
The goal of the axiomatic translation principle is to
find simplified theories, which
capture the inference problems in the original theory, but in a way
that is more amenable to automation and easier to deal with by existing
theorem provers.
The principle of the axiomatic translation is conceptually very simple
and can be largely automated.
Soundness is automatic under reasonable assumptions, and termination of
ordered resolution is easily achieved, but
the non-trivial part of the approach is proving completeness.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201812
urn:ISBN:3-540-40559-3
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction, Springer, 412-426 (2003)
en
oai:edoc.mpg.de:2018132012-09-1987:934
A Flexible and Versatile Studio for Multi-View Video Recording
Theobalt, Christian
Li, Ming
Magnor, Marcus
Seidel, Hans-Peter
Hall, Peter
Willis, Philip
In recent years, the convergence of computer vision and computer graphics has
put forth
new research areas that work on scene reconstruction from and analysis of
multi-view video
footage. In free-viewpoint video, for example, new views of a scene are
generated from an arbitrary viewpoint
in real-time using a set of multi-view video streams as inputs.
The analysis of real-world scenes from multi-view video
to extract motion information or reflection models is another field of research
that
greatly benefits from high-quality input data.
Building a recording setup for multi-view video involves a great effort on the
hardware
as well as the software side. The amount of image data to be processed is huge,
a decent lighting and camera setup is essential for a naturalistic scene
appearance and
robust background subtraction, and the computing infrastructure has to enable
real-time processing of the recorded material.
This paper describes our recording setup for multi-view video acquisition that
enables the
synchronized recording
of dynamic scenes from multiple camera positions under controlled conditions.
The requirements
to the room and their implementation in the separate components of the studio
are described in detail.
The efficiency and flexibility of the room is demonstrated on the basis of the
results
that we obtain with a real-time 3D scene reconstruction system, a system for
non-intrusive optical
motion capture and a model-based free-viewpoint video system for human actors.
Eurographics
2003
Conference-Paper
http://edoc.mpg.de/201813
urn:ISBN:3-905673-54-1
Vision, Video and Graphics 2003, Eurographics, 9-16 (2003)
en
oai:edoc.mpg.de:2018142012-09-1987:933
Estimating effective drug combinations against drug-resistant mutants from genotypes
Beerenwinkel, Niko
Däumer, Martin
Kaiser, Rolf
Walter, Hauke
Korn, Klaus
Hoffmann, Daniel
Selbig, Joachim
Lengauer, Thomas
European AIDS Clinical Society
2003
Conference-Paper
http://edoc.mpg.de/201814
Proceedings of the 1st European HIV Drug Resistamce Workshop, European AIDS Clinical Society, 18-18 (2003)
en
oai:edoc.mpg.de:2018152012-09-1987:930
Clustered Scheduling Algorithms for Mixed-Media Disk Workloads in a Multimedia Server
Balafoutis, Elias
Paterakis, Michael
Triantafillou, Peter
Nerjes, Guido
Muth, Peter
Weikum, Gerhard
2003
Article
http://edoc.mpg.de/201815
urn:ISSN:1386-7857
Cluster Computing, v.6, 75-86 (2003)
en
oai:edoc.mpg.de:2018162012-09-1987:934
Neural Meshes: Statistical Learning based on Normals
Jeong, Won-Ki
Ivrissimtzis, Ioannis
Seidel, Hans-Peter
Rokne, Jon
Klein, Reinhard
Wang, Wenping
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201816
urn:ISBN:0-7695-2028-6
11th Pacific Conference on Computer Graphics and Applications (PG-03), IEEE, 404-408 (2003)
en
oai:edoc.mpg.de:2018172012-09-1987:931
The complexity of economic equilibria for house allocation markets
Fekete, Sandor P.
Skutella, Martin
Woeginger, Gerhard J.
We prove NP-completeness of deciding the existence of an economic equilibrium
in so-called house allocation markets. House allocation markets are markets
with indivisible goods in which every agent holds exactly one copy of some
good.
2003
Article
http://edoc.mpg.de/201817
urn:ISSN:0020-0190
Information Processing Letters, v.88, 219-223 (2003)
en
oai:edoc.mpg.de:2018182012-09-1987:934
A Multi-scale Approach to 3D Scattered Data Interpolation with Compactly Supported Basis Functions
Ohtake, Yutaka
Belyaev, Alexander
Seidel, Hans-Peter
Kim, Myung-Soo
In this paper, we propose a hierarchical approach to 3D scattered
data interpolation with compactly supported basis functions.
Our numerical experiments suggest that the approach integrates
the best aspects of scattered data fitting with locally and globally
supported basis functions. Employing locally supported functions leads
to an efficient computational procedure, while a coarse-to-fine
hierarchy makes our method insensitive to the density of
scattered data and allows us to restore large parts of
missed data.
Given a point cloud distributed along a surface, we first use
spatial down sampling to construct a coarse-to-fine hierarchy
of point sets. Then we interpolate the sets starting from the
coarsest level. We interpolate a point set of the hierarchy,
as an offsetting of the interpolating function computed at
the previous level. Fig.\,\ref{risu_multi} shows an original
point set (the leftmost image) and its coarse-to-fine hierarchy
of interpolated sets.
According to our numerical experiments, the method
is essentially faster than the state-of-art scattered data
approximation with globally supported RBFs \cite{rbf}
and much simpler to implement.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201818
Shape Modeling International 2003 (SMI 2003), IEEE, 153-161 (2003)
en
oai:edoc.mpg.de:2018192012-09-1987:934
Exploiting Temporal Coherence in Ray Casted Walkthroughs
Havran, Vlastimil
Bittner, Jiri
Seidel, Hans-Peter
Joy, Kenneth I.
We present a technique that aims at exploiting temporal coherence of ray casted
walkthroughs. Our goal is to reuse ray/object
intersections computed in the last frame of the walkthrough for
acceleration of ray casting in the current frame. In particular we aim at
eliminating the ray traversal and computing only a single ray/object
intersection per pixel. If our technique does not succeed in determining
visibility, it falls back to the classical ray traversal. Visible point samples
from the last frame are reprojected to the current frame. To identify whether
these samples can be reused we apply splatting and epipolar geometry
constraints. We discuss two additional techniques that handle correct
appearance of small objects. We conducted a series of tests on walkthroughs of
building interiors. Our method succeeded in determining visibility of more than
78\% of pixels. For these pixels only a single ray/object intersection is
executed. The frame rate is increased by up to 47\%. Finally, we
argue that the achieved speedup is relatively significant by comparing the
performance of our algorithm to the ``ideal'' ray shooting algorithm.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201819
Proceedings of the 19th Spring Conference on Computer Graphics 2003 (SCCG 03), ACM, 164-172 (2003)
en
oai:edoc.mpg.de:2018202012-09-1987:934
Construction and Animation of Anatomically Based Human Hand Models
Albrecht, Irene
Haber, Jörg
Seidel, Hans-Peter
Breen, Dave
Lin, Ming
The human hand is a masterpiece of mechanical complexity, able to perform
fine motor manipulations and powerful work alike. Designing an animatable
human hand model that features the abilities of the archetype created by
Nature requires a great deal of anatomical detail to be modeled. In this
paper, we present a human hand model with underlying anatomical
structure. Animation of the hand model is controlled by muscle contraction
values. We employ a physically based hybrid muscle model to convert these
contraction values into movement of skin and bones. Pseudo muscles directly
control the rotation of bones based on anatomical data and mechanical laws,
while geometric muscles deform the skin tissue using a mass-spring
system. Thus, resulting animations automatically exhibit anatomically and
physically correct finger movements and skin deformations. In addition, we
present a deformation technique to create individual hand models from
photographs. A radial basis warping function is set up from the
correspondence of feature points and applied to the complete structure of
the reference hand model, making the deformed hand model instantly
animatable.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201820
urn:ISBN:1-58113-659-5
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SIGGRAPH-SCA-03), ACM, 98-109,368 (2003)
en
oai:edoc.mpg.de:2018212012-09-1987:934
MEDUSA - A Facial Modeling and Animation System
Haber, Jörg
Plesser, Theo
Macho, Volker
Gesellschaft für Wissenschaftliche Datenverarbeitung Göttingen
2003
InBook
http://edoc.mpg.de/201821
urn:ISSN:0176-2516
Forschung und wissenschaftliches Rechnen - Beiträge zum Heinz-Billing-Preis 2001, 13-28 (2003)
en
oai:edoc.mpg.de:2018222010-12-0287:932
Universal variables in disconnection tableaux
Letz, Reinhold
Stenz, Gernot
Cialdea Mayer, Marta
Pirri, Fiora
Springer
2003
Conference-Paper
http://edoc.mpg.de/201822
urn:ISBN:3-540-40787-1
Automated reasoning with analytical tableaux and related methods : International Conference, TABLEAUX 2003, Springer, 117-133 (2003)
en
oai:edoc.mpg.de:2018232010-12-0287:932
The New WALDMEISTER Loop at Work
Gaillourdet, Jean-Marie
Hillenbrand, Thomas
Löchner, Bernd
Spies, Hendrik
Baader, Franz
We present recent developments within the theorem prover \textsc{Waldmeister}.
They rely on a novel organization of the underlying saturation-based proof
procedure into a system architecture. As is known, the saturation process tends
to quickly fill the memory available unless preventive measures are employed.
To overcome this problem, our new ``\textsc{Waldmeister} loop'' features a
highly compact representation of the search state, exploiting its inherent
structure. The implementation just being available, the cost and the benefits
of the concept now can exactly be measured. Indeed are our expectations met
concerning the drastic cut-down of memory usage with only moderate overhead of
time.
In addition it has turned out that the revealed structure of the search state
paves the way to an easily implemented parallelization of the prover with
modest communication requirements and rewarding speed-ups. In order to minimize
communication-related latencies, we discuss some variations of the loop to
maximally profit from multiple processors.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201823
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction, Springer, 317-321 (2003)
en
oai:edoc.mpg.de:2018242012-09-1987:934
An Efficient Spatio-Temporal Architecture for Animation Rendering
Havran, Vlastimil
Damez, Cyrille
Myszkowski, Karol
Seidel, Hans-Peter
Christensen, Per
Cohen-Or, Daniel
Producing high quality animations featuring rich object appearance and
compelling lighting effects is very time consuming using traditional
frame-by-frame rendering systems. In this paper we present a rendering
architecture for computing multiple frames at once by exploiting the coherence
between image samples in the temporal domain. For each sample representing a
given point in the scene we update its view-dependent components for each frame
and add its contribution to pixels identified through the compensation of
camera and object motion. This leads naturally to a high quality motion blur
and significantly reduces the cost of illumination computations. The required
visibility information is provided using a custom ray tracing acceleration data
structure for multiple frames simultaneously. We demonstrate that precise
and costly global illumination techniques such as bidirectional path tracing
become affordable in this rendering architecture.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201824
urn:ISBN:1-58113-754-0
Rendering Techniques 2003 : 14th Eurographics Workshop on Rendering, ACM, 106-117 (2003)
en
oai:edoc.mpg.de:2018252012-09-1987:934
Online Accelerated Rendering of Visual Hulls in Real Scenes
Li, Ming
Magnor, Marcus
Seidel, Hans-Peter
This paper presents an online system which is capable of reconstructing and
rendering dynamic objects in real scenes. We reconstruct visual hulls of the
objects by using a shape-from-silhouette approach. During rendering, a novel
blending scheme is employed to compose multiple background images. Visibility
artifacts on the dynamic object are removed by using opaque projective texture
mapping. We also propose a dynamic texture packing technique to improve
rendering performance by exploiting region-of-interest information. Our system
takes multiple live or pre-recorded video streams as input. It produces
realistic real-time rendering results of dynamic objects in their surrounding
natural environment in which the user can freely navigate.
2003
Article
http://edoc.mpg.de/201825
urn:ISSN:1213-6972
Journal of WSCG, v.11, 290-297 (2003)
en
oai:edoc.mpg.de:2018262010-12-0387:937
Online Accelerated Rendering of Visual Hulls in Real Scenes
Li, Ming
Magnor, Marcus
Seidel, Hans-Peter
This paper presents an online system which is capable of reconstructing and
rendering dynamic objects in real scenes. We reconstruct visual hulls of the
objects by using a shape-from-silhouette approach. During rendering, a novel
blending scheme is employed to compose multiple background images. Visibility
artifacts on the dynamic object are removed by using opaque projective texture
mapping. We also propose a dynamic texture packing technique to improve
rendering performance by exploiting region-of-interest information. Our system
takes multiple live or pre-recorded video streams as input. It produces
realistic real-time rendering results of dynamic objects in their surrounding
natural environment in which the user can freely navigate.
2003
Article
http://edoc.mpg.de/201826
urn:ISSN:1213-6972
Journal of WSCG, v.11, 290-297 (2003)
en
oai:edoc.mpg.de:2018272012-09-1987:931
Algorithms and Experiments for the Webgraph
Laura, Luigi
Leonardi, Stefano
Millozzi, Stefano
Meyer, Ulrich
Sibeyn, Jop F.
Di Battista, Giuseppe
Zwick, Uri
Springer
2003
Conference-Paper
http://edoc.mpg.de/201827
urn:ISSN:0302-9743
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 703-714 (2003)
en
oai:edoc.mpg.de:2018282012-09-1987:934
Interactive Rendering of Translucent Deformable Objects
Mertens, Tom
Kautz, Jan
Bekaert, Philippe
Seidel, Hans-Peter
Van Reeth, Frank
Christensen, Per
Cohen-Or, Daniel
ACM
2003
Conference-Paper
http://edoc.mpg.de/201828
urn:ISSN:1727-3463
Rendering Techniques 2003 : 14th Eurographics Workshop on Rendering, ACM, 130-140 (2003)
en
oai:edoc.mpg.de:2018292012-09-1987:931
Reconciling simplicity and realism in parallel disk models
Sanders, Peter
For the design and analysis of algorithms that process huge data sets, a
machine model is needed that handles parallel disks. There seems to be
a dilemma between simple and flexible use of such a model and accurate
modelling of details of the hardware. This paper explains how many
aspects of this problem can be resolved. The programming model
implements one large logical disk allowing concurrent access to
arbitrary sets of variable size blocks. This model can
be implemented efficienctly on multiple
independent disks even if zones with different speed,
communication bottlenecks
and failed disks are allowed. These results not only provide useful
algorithmic tools but also imply a theoretical justification for
studying external memory algorithms using simple abstract models.
The algorithmic approach is random redundant placement of data and
optimal scheduling of accesses. The analysis generalizes a previous
analysis for simple abstract external memory models in several ways
(Higher efficiency, variable block sizes, more detailed disk model).
As a side effect, an apparently new Chernoff-Hoeffding bound for sums of
weighted 0-1 random variables is derived.
2002
Article
http://edoc.mpg.de/201829
urn:ISSN:0167-8191
Parallel Computing, v.28, 705-723 (2002)
en
oai:edoc.mpg.de:2018302010-12-0387:936
Bounds on the Chvátal rank of Polytopes in the 0/1 Cube
Eisenbrand, Friedrich
Schulz, Andreas S.
Gomory's and Chvátal's cutting-plane procedure proves recursively
the validity of linear inequalities for the integer hull of a given
polyhedron. The number of rounds needed to obtain all valid
inequalities is known as the Chvátal rank of the polyhedron. It is
well-known that the Chvátal rank can be arbitrarily large, even if
the polyhedron is bounded, if it is of dimension $2$, and if its
integer hull is a $0/1$-polytope.
We prove that the Chvátal rank of polyhedra featured in common
relaxations of many combinatorial optimization problems is rather small;
in fact, the rank of any polytope contained in the $n$-dimensional
$0/1$-cube is at most $3 n^2 \lg n$. This improves upon a recent
result of Bockmayr et al.\ \cite{BEHS99} who obtained an upper bound of
$\text{O}(n^3 \log n)$.
Moreover, we refine this result by showing that the rank of any
polytope in the $0/1$-cube that is defined by inequalities with
small coefficients is $\text{O}(n)$. The latter observation explains
why for most cutting planes derived in polyhedral studies of several
popular combinatorial optimization problems only linear growth has
been observed (see, e.g., \cite{ChvatalCookHartmann89}); the
coefficients of the corresponding inequalities are usually small.
Similar results were only known
for monotone polyhedra before.
Finally, we provide a family of polytopes contained in the
$0/1$-cube the Chvátal rank of which is at least $(1+e) n$
for some $e > 0$; the
best known lower bound was $n$.
2003
Article
http://edoc.mpg.de/201830
urn:ISSN:1439-6912
Combinatorica, v.23, 245-261 (2003)
en
oai:edoc.mpg.de:2018312010-12-0387:936
Primal Separation for 0/1 Polytopes
Eisenbrand, Friedrich
Rinaldi, Giovanni
Ventura, Paolo
\noindent
The 0/1~primal separation problem is: Given an extreme point $\bar{x}$ of a
0/1~polytope $P$ and some point $x^*$, find an inequality which is
tight at $\bar{x}$, violated by $x^*$ and valid for $P$ or assert that
no such inequality exists. It is known
that this separation variant can be reduced to the standard
separation problem for $P$.
\noindent
We show that 0/1~optimization and 0/1~primal separation
are polynomial time equivalent. This implies that the problems
0/1~optimization, 0/1~standard separation, 0/1~augmentation, and
0/1~primal separation are polynomial time equivalent.
\noindent
Then we provide polynomial time primal separation procedures for
matching, stable set, maximum cut, and maximum bipartite graph
problems, giving evidence that these algorithms are conceptually
simpler and easier to implement than their corresponding counterparts
for standard separation. In particular, for perfect matching we
present an algorithm for primal separation that rests only on simple
max-flow computations. In contrast, the known standard separation
method relies on an explicit minimum odd cut algorithm. Consequently,
we obtain a very simple proof that a maximum weight perfect matching
of a graph can be computed in polynomial time.
2003
Article
http://edoc.mpg.de/201831
urn:ISSN:0025-5610
Mathematical Programming / A, v.95, 475-491 (2003)
en
oai:edoc.mpg.de:2018322012-09-1987:933
Geno2pheno: estimating phenotypic drug resistance from HIV-1 genotypes
Beerenwinkel, Niko
Däumer, Martin
Oette, Mark
Korn, Klaus
Hoffmann, Daniel
Kaiser, Rolf
Lengauer, Thomas
Selbig, Joachim
Walter, Hauke
2003
Article
http://edoc.mpg.de/201832
Nucleic Acids Research, v.31, 3850-3855 (2003)
en
oai:edoc.mpg.de:2018332012-09-1987:934
Planned Sampling of Spatially Varying BRDFs
Lensch, Hendrik P. A.
Lang, Jochen
Sá, Asla M.
Seidel, Hans-Peter
Brunet, Pere
Fellner, Dieter W.
Blackwell
2003
Conference-Paper
http://edoc.mpg.de/201833
urn:ISSN:0167-7055
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference, Blackwell, 473-482 (2003)
en
oai:edoc.mpg.de:2018342012-09-1987:931
Approximating Energy Efficient Paths in Wireless Multi-hop Networks
Funke, Stefan
Matijevic, Domagoj
Sanders, Peter
Di Battista, Giuseppe
Zwick, Uri
Given the positions of $n$ sites in a radio network
we consider the problem of finding routes between any pair of sites
that minimize energy consumption and do not use more than some
constant number $k$ of hops. Known exact algorithms for this problem
required $\Omega(n \log n)$ per query pair $(p,q)$. In this paper we
relax the exactness requirement and only require approximate
$(1+\epsilon)$ solutions which allows us to derive schemes which
guarantee constant query time using linear space and
$O(n\log n)$ preprocessing time. The dependence on $\epsilon$ is
polynomial in $1/\epsilon$.
One tool used might be of independent interest:
For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$
report in constant time the cluster pair $(A,B)$ representing $(p,q)$
in a well-separated pair decomposition of $P$.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201834
urn:ISBN:3-540-20064-9
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 230-241 (2003)
en
oai:edoc.mpg.de:2018352012-09-1987:931
On the Competitive Ratio for Online Facility Location
Fotakis, Dimitris
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.
We consider the problem of Online Facility Location, where demands arrive
online and must be irrevocably assigned to an open facility upon arrival. The
objective is to minimize the sum of facility and assignment costs. We prove
that the competitive ratio for Online Facility Location is $\Theta(\frac{\log
n}{\log\log n})$. On the negative side, we show that no randomized algorithm
can achieve a competitive ratio better than $O(\frac{\log n}{\log\log n})$
against an oblivious adversary even if the demands lie on a line segment. On
the positive side, we present a deterministic algorithm achieving a competitive
ratio of $O(\frac{\log n}{\log\log n})$. The analysis is based on a
hierarchical decomposition of the optimal facility locations such that each
component either is relatively well-separated or has a relatively large
diameter, and a potential function argument which distinguishes between the two
kinds of components.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201835
urn:ISBN:3-540-40493-7
Automata, languages and programming : 30th International Colloquium, ICALP 2003, Springer, 637-652 (2003)
en
oai:edoc.mpg.de:2018372012-09-1987:934
Shadow Volumes on Programmable Graphics Hardware
Brabec, Stefan
Seidel, Hans-Peter
Brunet, Pere
Fellner, Dieter W.
One of the best choices for fast, high quality shadows is the shadow
volume algorithm. However, for real time applications the extraction
of silhouette edges can significantly burden the CPU, especially
with highly tessellated input geometry or when complex geometry
shaders are applied.
In this paper we show how this last, expensive part of the shadow
volume method can be implemented on programmable graphics hardware.
This way, the originally hybrid shadow volumes algorithm can now be
reformulated as a purely hardware-accelerated approach.
The benefits of this implementation is not only the increase in speed.
Firstly, all computations now run on the same hardware
resulting in consistent precision within all steps of the
algorithm. Secondly, programmable vertex transformations
are no longer problematic when applied to shadow casting objects.
Blackwell
2003
Conference-Paper
http://edoc.mpg.de/201837
urn:ISSN:0167-7055
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference, Blackwell, 433-440 (2003)
en
oai:edoc.mpg.de:2018382012-09-1987:934
Feature Flow Fields
Theisel, Holger
Seidel, Hans-Peter
Bonneau, Georges-Pierre
Hahmann, Stefanie
Hansen, Charles
Spencer, Stephen N.
Eurographics
2003
Conference-Paper
http://edoc.mpg.de/201838
Data Visualisation 2003 (VisSym-03) : Joint Eurographics / IEEE TCVG Symposium on Visualization, Eurographics, 141-148 (2003)
en
oai:edoc.mpg.de:2018392012-09-1987:934
Visualization of Volume Data with Quadratic Super Splines
Rössl, Christian
Zeilfelder, Frank
Nürnberger, Günther
Seidel, Hans-Peter
Turk, Greg
van Wijk, Jarke
Moorhead, Robert
We develop a new approach to reconstruct non-discrete models from
gridded volume samples. As a model, we use quadratic trivariate super
splines on a uniform tetrahedral partition . The approximating splines
are determined in a natural and completely symmetric way by averaging
local data samples, such that appropriate smoothness conditions are
automatically satisfied. On each tetrahedron of , the
quasi-interpolating spline is a polynomial of total degree two which
provides several advantages including efficient computation,
evaluation and visualization of the model. We apply Bernstein-B´ezier
techniques well-known in CAGD to compute and evaluate the trivariate
spline and its gradient. With this approach the volume data can be
visualized efficiently e.g. with isosurface raycasting. Along an
arbitrary ray the splines are univariate, piecewise quadratics and
thus the exact intersection for a prescribed isovalue can be easily
determined in an analytic and exact way. Our results confirm the
efficiency of the quasi-interpolating method and demonstrate high
visual quality for rendered isosurfaces.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201839
IEEE Visualization 2003 (VIS-03), IEEE, 393-400 (2003)
en
oai:edoc.mpg.de:2018402012-09-1987:934
Reanimating Faces in Images and Video
Blanz, Volker
Basso, Curzio
Vetter, Thomas
Poggio, Tomaso
Brunet, Pere
Fellner, Dieter W.
This paper presents a method
for photo-realistic animation that can be applied to
any face shown in a single image or a video.
The technique does not require example data of the person's mouth movements,
and the image to be animated is not restricted in pose or illumination.
Video reanimation allows for head rotations and speech in the original sequence,
but neither of these motions is required.
In order to animate novel faces, the system
transfers mouth movements and expressions across individuals,
based on a common representation of different identities and facial expressions
in a vector space of 3D shapes and textures.
This space is computed from 3D scans of different neutral faces,
and scans of facial expressions.
The 3D model's versatility with respect to pose and illumination
is conveyed to photo-realistic image and video processing
by a framework of analysis and synthesis algorithms:
The system automatically estimates 3D shape
and all relevant rendering parameters, such as pose, from single images.
In video, head pose and mouth movements are tracked automatically.
Reanimated with new mouth movements, the 3D face is rendered
into the original images.
Blackwell
2003
Conference-Paper
http://edoc.mpg.de/201840
urn:ISSN:0167-7055
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference, Blackwell, 641-650 (2003)
en
oai:edoc.mpg.de:2018422012-09-1987:933
Efficient Clustering Methods for Tumor Classification with Microarrays
Rahnenführer, Jörg
Schader, Martin
Gaul, Wolfgang
Vichi, Maurizio
Springer
2003
Conference-Paper
http://edoc.mpg.de/201842
Proceedings of the 26th Annual Conference of the Gesellschaft für Klassifikation, Springer, 670-679 (2003)
en
oai:edoc.mpg.de:2018432012-09-1987:934
Dynamic Remeshing and Applications
Vorsatz, Jens
Rössl, Christian
Seidel, Hans-Peter
Elber, Gershon
Shapiro, Vadim
Triangle meshes are a flexible and generally accepted boundary
representation for complex geometric shapes. In addition to their
geometric qualities and topological simplicity, \emph{intrinsic}
qualities such as the shape of the triangles, their distribution on
the surface and the connectivity are essential for many algorithms
working on them. In this paper we present a flexible and efficient
remeshing framework that improves these intrinsic properties while
keeping the mesh geometrically close to the original surface. We
use a particle system approach and combine it with an incremental
connectivity optimization process to trim the mesh towards the
requirements imposed by the user. The particle system uniformly
distributes the vertices on the mesh, whereas the connectivity
optimization is done by means of \emph{Dynamic Connectivity Meshes},
a combination of local topological operators that lead to a fairly
regular connectivity. A dynamic skeleton ensures that our approach
is able to preserve surface features, which are particularly
important for the visual quality of the mesh. None of the
algorithms requires a global parameterization or patch layouting in
a preprocessing step but uses local parameterizations only. We also
show how this general framework can be put into practice and sketch
several application scenarios. In particular we will show how the
users can adapt the involved algorithms in a way that the resulting
remesh meets their personal requirements.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201843
Proceedings: 8th ACM Symposium on Solid Modeling and Applications (SM-03), ACM, 167-175 (2003)
en
oai:edoc.mpg.de:2018442012-09-1987:931
Simple Linear Work Suffix Array Construction
Kärkkäinen, Juha
Sanders, Peter
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.
A suffix array represents the suffixes of a string in sorted order.
Being a simpler and more compact alternative to suffix trees, it
is an important tool for full text indexing and other string
processing tasks. We introduce the \emph{skew algorithm}
for suffix array construction over integer alphabets that can be
implemented to run in linear time using integer sorting as its only
nontrivial subroutine:\\
1. recursively sort suffixes beginning at positions $i\bmod 3\neq 0$.\\
2. sort the remaining suffixes using the information
obtained in step one.\\
3. merge the two sorted sequences obtained in steps one and two.\\
The algorithm is much
simpler than previous linear time algorithms that
are all based on the more complicated suffix tree data structure.
Since sorting is a well studied problem, we obtain
optimal algorithms for several other models of computation,
e.g.\ external memory with parallel disks, cache oblivious,
and parallel. The adaptations for BSP and EREW-PRAM
are asymptotically faster than the best previously known algorithms.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201844
urn:ISBN:3540404937
Automata, languages and programming : 30th International Colloquium, ICALP 2003, Springer, 943-955 (2003)
en
oai:edoc.mpg.de:2018452012-09-1987:934
Reanimating the Dead: Reconstruction of Expressive Faces from Skull Data
Kähler, Kolja
Haber, Jörg
Seidel, Hans-Peter
Hodgins, Jessica K.
Facial reconstruction for postmortem identification of humans from
their skeletal remains is a challenging and fascinating part of
forensic art. The former look of a face can be approximated by
predicting and modeling the layers of tissue on the skull.
This work is as of today carried out solely by physical sculpting
with clay, where experienced artists invest up to hundreds of hours
to craft a reconstructed face model. Remarkably, one of the most
popular tissue reconstruction methods bears many resemblances with
surface fitting techniques used in computer graphics, thus
suggesting the possibility of a transfer of the manual approach to
the computer. In this paper, we present a facial reconstruction
approach that fits an anatomy-based virtual head model,
incorporating skin and muscles, to a scanned skull using
statistical data on skull / tissue relationships. The approach has
many advantages over the traditional process: a reconstruction can
be completed in about an hour from acquired skull data; also,
variations such as a slender or a more obese build of the modeled
individual are easily created. Last not least, by matching not only
skin geometry but also virtual muscle layers, an animatable head
model is generated that can be used to form facial expressions
beyond the neutral face typically used in physical
reconstructions.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201845
urn:ISSN:0730-0301
Proceedings of ACM SIGGRAPH 2003 (SIGGRAPH-03), ACM, 554-561 (2003)
en
oai:edoc.mpg.de:2018462012-09-1987:934
Component-based Face Recognition with 3D Morphable Models
Huang, Jennifer
Heisele, Bernd
Blanz, Volker
Kittler, Josef
Nixon, Mark S.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201846
International Conference on Audio- and Video-Based Biometric Person Authentication (AVBPA-03), Springer, 27-34 (2003)
en
oai:edoc.mpg.de:2018472010-12-0387:937
Fast Hologram Synthesis for 3D Geometry Models using Graphics Hardware
Petz, Christoph
Magnor, Marcus
Jeong, Tung H.
Stevenson, Sylvia H.
The holographic visualization of three-dimensional object geometry still
represents a major challenge in computational holography research. Besides the
development of suitable holographic display devices, the fast calculation of the
hologram's interference pattern for complex-shaped three-dimensional objects is
an important pre-requisite of any interactive holographic display system. We
present a fast method for rendering full-parallax holograms using a standard PC
with a consumer-market graphics card. To calculate the hologram of a 3D
object, scaled and translated versions of the interference pattern of simple
primitives, e.g. point sources, are superimposed. The
hologram is built up completely
on-board the graphics card.
To avoid numerical inaccuracies due to limited
frame-buffer resolution, we use a hierarchical approach.
Using an NVidia
Geforce4 graphics card, the proposed
algorithm takes 1.0 second to calculate the 512x512-pixel hologram of 1024
primitives.
SPIE
http://www.mpi-sb.mpg.de/~petz/holography.html
2003
Conference-Paper
http://edoc.mpg.de/201847
urn:ISBN:0-8194-4805-2
Practical Holography XVII and Holographic Materials IX, SPIE, 266-275 (2003)
en
oai:edoc.mpg.de:2018482012-09-1987:934
Subdivision Rules for General Meshes
Ivrissimtzis, Ioannis
Shrivastava, Kanishka
Seidel, Hans-Peter
Cohen, Albert
Merrien, Jean-Louis
Schumaker, Larry L.
Nashboro Press
2003
Conference-Paper
http://edoc.mpg.de/201848
urn:ISBN:0-9728482-1-5
Curve and Surface Fitting: Saint-Malo 2002, Nashboro Press, 229-238 (2003)
en
oai:edoc.mpg.de:2018492012-09-1987:933
Statistical Inference for Clustering Microarrays
Rahnenführer, Jörg
Denison, David D.
Hansen, Mark H.
Holmes, Christopher C.
Mallick, Bani
Yu, Bin
Springer
2003
Conference-Paper
http://edoc.mpg.de/201849
Proceedings of the MSRI Workshop: Nonlinear Estimation and Classification, Springer, 323-332 (2003)
en
oai:edoc.mpg.de:2018502012-09-1987:931
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers?
Dhiflaoui, Marcel
Funke, Stefan
Kwappik, Carsten
Mehlhorn, Kurt
Seel, Michael
Schömer, Elmar
Schulte, Ralph
Weber, Dennis
ACM
2003
Conference-Paper
http://edoc.mpg.de/201850
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 255-256 (2003)
en
oai:edoc.mpg.de:2018512012-09-1987:931
Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location
Hoefer, Martin
Jansen, Klaus
Margraf, Marian
Mastrolli, Monaldo
Rolim, José D. P.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201851
urn:ISBN:3-540-40205-5
Experimental and efficient algorithms : Second International Workshop, WEA 2003, Springer, 165-178 (2003)
en
oai:edoc.mpg.de:2018522010-12-0287:932
Software Model Checking with Abstraction Refinement
Podelski, Andreas
Zuck, Lenore
Attie, Paul
Cortesi, Agostino
Mukhopadhyay, Supratik
Springer
2003
Conference-Paper
http://edoc.mpg.de/201852
urn:ISBN:3-540-00348-7
Verification, model checking, and abstract interpretation : 4th International Conference, VMCAI 2003, Springer, 1-13 (2003)
en
oai:edoc.mpg.de:2018532010-12-0287:932
Superposition modulo a Shostak Theory
Ganzinger, Harald
Hillenbrand, Thomas
Waldmann, Uwe
Baader, Franz
We investigate superposition modulo a Shostak theory $T$ in order to
facilitate reasoning in the amalgamation of $T$ and a free
theory~$F$.
%
Free operators occur naturally e.\,g.\ in program verification
problems when abstracting over subroutines. If their behaviour in
addition can be specified axiomatically, much more of the program
semantics can be captured.
%
Combining the Shostak-style components for deciding the clausal
validity problem with the ordering and saturation techniques
developed for equational reasoning, we derive a refutationally
complete calculus on mixed ground clauses which result for example
from CNF transforming arbitrary universally quantified formulae.
%
The calculus works modulo a Shostak theory in the sense that it
operates on canonizer normalforms. For the Shostak solvers that we
study, coherence comes for free: no coherence pairs need to be
considered.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201853
urn:ISBN:3-540-40559-3
Automated Deduction, CADE-19 : 19th International Conference on Automated Deduction, Springer, 182-196 (2003)
en
oai:edoc.mpg.de:2018542010-12-0387:937
Real-time, Free-viewpoint Video Rendering from Volumetric Geometry
Goldluecke, Bastian
Magnor, Marcus
Ebrahimi, Touradj
Sikora, Thomas
The aim of this work is to render high-quality views of a dynamic scene
from novel viewpoints in real-time. An online system available at our institute
computes the visual hull as a geometry proxy to guide the rendering at
interactive rates. Because only a sparse set of cameras distributed around the
scene is used to record the scene, only an coarse model of the scene geometry
can be recovered. To alleviate this problem, we render textured billboards
defined by the voxel model of the visual hull, preserving details in the source
images while
achieving excellent performance. By exploiting multi-texturing capabilities of
modern graphics hardware, real-time frame rates are attained. Our algorithm can
be used as part of an inexpensive system to display 3D-videos, or ultimately
even in live 3D-television. The user is able to watch the scene from an
arbitrary viewpoint chosen interactively.
SPIE
2003
Conference-Paper
http://edoc.mpg.de/201854
urn:ISBN:0-8194-5023-5
Visual Communications and Image Processing 2003, SPIE, 1152-1158 (2003)
en
oai:edoc.mpg.de:2018552012-09-1987:934
Efficient Rendering of Local Subsurface Scattering
Mertens, Tom
Kautz, Jan
Bekaert, Philippe
Seidel, Hans-Peter
Van Reeth, Frank
Rokne, Jon
Klein, Reinhard
Wang, Wenping
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201855
11th Pacific Conference on Computer Graphics and Applications (PG-03), IEEE, 51-58 (2003)
en
oai:edoc.mpg.de:2018562010-12-0387:937
A Flexible and Versatile Studio for Synchronized Multi-view Video Recording
Theobalt, Christian
Li, Ming
Magnor, Marcus
Seidel, Hans-Peter
Hall, Peter
Willis, Philip
In recent years, the convergence of computer vision and computer graphics has
put forth
new research areas that work on scene reconstruction from and analysis of
multi-view video
footage. In free-viewpoint video, for example, new views of a scene are
generated from an arbitrary viewpoint
in real-time using a set of multi-view video streams as inputs.
The analysis of real-world scenes from multi-view video
to extract motion information or reflection models is another field of research
that
greatly benefits from high-quality input data.
Building a recording setup for multi-view video involves a great effort on the
hardware
as well as the software side. The amount of image data to be processed is huge,
a decent lighting and camera setup is essential for a naturalistic scene
appearance and
robust background subtraction, and the computing infrastructure has to enable
real-time processing of the recorded material.
This paper describes our recording setup for multi-view video acquisition that
enables the
synchronized recording
of dynamic scenes from multiple camera positions under controlled conditions.
The requirements
to the room and their implementation in the separate components of the studio
are described in detail.
The efficiency and flexibility of the room is demonstrated on the basis of the
results
that we obtain with a real-time 3D scene reconstruction system, a system for
non-intrusive optical
motion capture and a model-based free-viewpoint video system for human actors.
Eurographics
2003
Conference-Paper
http://edoc.mpg.de/201856
urn:ISBN:3-905673-54-1
Vision, Video, and Graphics 2003, Eurographics, 9-16 (2003)
en
oai:edoc.mpg.de:2018572012-09-1987:931
Space Efficient Hash Tables with Worst Case Constant Access Time
Fotakis, Dimitris
Pagh, Rasmus
Sanders, Peter
Spirakis, Paul G.
Alt, Helmut
Habib, Michel
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing}
and show how this yields a simple hash table data structure that stores $n$
elements in $(1+\epsilon)\,n$ memory cells, for any constant $\epsilon > 0$.
Assuming uniform hashing, accessing or deleting table entries takes at most $d
= O(\ln\frac{1}{\epsilon})$ probes and the expected amortized insertion time is
constant. This is the first dictionary that has worst case constant access time
and expected constant update time, works with $(1+\epsilon)\,n$ space, and
supports satellite information. Experiments indicate that $d=4$ choices suffice
for $\epsilon \approx 0.03$. We also describe a hash table data structure using
explicit constant time hash functions, using at most $d=
O(\ln^2\frac{1}{\epsilon})$ probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum
cardinality matchings in a rather natural model of sparse random bipartite
graphs.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201857
urn:ISBN:3-540-00623-0
Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), Springer, 271-282 (2003)
en
oai:edoc.mpg.de:2018582012-09-1987:934
Saddle Connectors - An Approach to Visualizing the Topological Skeleton of Complex 3D Vector Fields
Theisel, Holger
Weinkauf, Tino
Hege, Hans-Christian
Seidel, Hans-Peter
Turk, Greg
van Wijk, Jarke
Moorhead, Robert
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201858
IEEE Visualization 2003 (VIS-03), IEEE, 225-232 (2003)
en
oai:edoc.mpg.de:2018592012-09-1987:931
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property
Katriel, Irit
Sanders, Peter
Träff, Jesper Larsson
Di Battista, Giuseppe
Zwick, Uri
Springer
2003
Conference-Paper
http://edoc.mpg.de/201859
urn:ISBN:3540200649
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 679-690 (2003)
en
oai:edoc.mpg.de:2018602012-09-1987:933
Combinatorial Optimization Techniques for Three-Dimensional Arrangement Problems
Lengauer, Thomas
Schäfer, M.
Jäger, Willi
Krebs, Hans-Joachim
Springer
2003
InBook
http://edoc.mpg.de/201860
Mathematics - Key Technology for the Future, 63-73 (2003)
en
oai:edoc.mpg.de:2018612012-09-1987:931
Memory hierarchies - models and lower bounds
Sanders, Peter
Meyer, Ulrich
Sanders, Peter
Sibeyn, Jop
Springer
2003
InBook
http://edoc.mpg.de/201861
urn:ISBN:3-540-00883-7
Algorithms for memory hierarchies, 1-10 (2003)
en
oai:edoc.mpg.de:2018622012-09-1987:934
Adaptive Logarithmic Mapping For Displaying High Contrast Scenes
Drago, Frederic
Myszkowski, Karol
Annen, Thomas
Chiba, Norishige
Brunet, Pere
Fellner, Dieter W.
We propose a fast, high quality tone mapping technique to display high contrast
images
on devices with limited dynamic range of luminance values. The method is based
on
logarithmic compression of luminance values, imitating the human response to
light.
A bias power function is introduced to adaptively vary logarithmic bases,
resulting in good
preservation of details and contrast. To improve contrast in dark areas,
changes to
the gamma correction procedure are proposed. Our adaptive logarithmic mapping
technique is
capable of producing perceptually tuned images with high dynamic content and
works
at interactive speeds. We demonstrate a successful application of our technique
to a high dynamic range video player which enables to
adjust optimal viewing conditions for any kind of display while taking
into account the user preferences concerning brightness, contrast compression,
and detail
reproduction.
Blackwell
2003
Conference-Paper
http://edoc.mpg.de/201862
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference, Blackwell, 419-426 (2003)
en
oai:edoc.mpg.de:2018632012-09-1987:931
Nearest Neighbors Can Be Found Efficiently If the Dimension Is Small Relative to the Input Size
Hagedoorn, Michiel
Calvanese, Diego
Lenzerini, Maurizio
Motwani, Rajeev
Springer
The copyright for this distribution is held by Springer.
© Springer-Verlag
http://www.springer.de/comp/lncs/index.html
2003
Conference-Paper
http://edoc.mpg.de/201863
urn:ISBN:3-540-00323-1
Database Theory - ICDT 2003 : 9th International Conference, Springer, 440-454 (2003)
en
oai:edoc.mpg.de:2018642012-09-1987:931
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
Krysta, Piotr
Sanders, Peter
Vöcking, Berthold
Rovan, Branislav
Vojtáš, Peter
Springer
2003
Conference-Paper
http://edoc.mpg.de/201864
urn:ISBN:3540406719
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003, Springer, 500-510 (2003)
en
oai:edoc.mpg.de:2018652012-09-1987:934
Characteristics of dual-sqrt(3) subdivision schemes
Dodgson, Neil
Ivrissimtzis, Ioannis
Sabin, Malcolm
Cohen, Albert
Merrien, Jean-Louis
Schumaker, Larry L.
Nashboro Press
2003
Conference-Paper
http://edoc.mpg.de/201865
urn:ISBN:0-9728482-1-5
Curve and Surface Fitting: Saint-Malo 2002, Nashboro Press, 119-128 (2003)
en
oai:edoc.mpg.de:2018662012-09-1987:934
Interactive Rendering of Translucent Objects
Lensch, Hendrik P. A.
Goesele, Michael
Bekaert, Philippe
Kautz, Jan
Magnor, Marcus
Lang, Jochen
Seidel, Hans-Peter
This paper presents a rendering method for translucent objects, in which
viewpoint and illumination can be
modified at interactive rates. In a preprocessing step, the impulse response to
incoming light impinging at each
surface point is computed and stored in two different ways: The local effect on
close-by surface points is modeled
as a per-texel filter kernel that is applied to a texture map representing the
incident illumination. The global
response (i.e. light shining through the object) is stored as vertex-to-vertex
throughput factors for the triangle
mesh of the object. During rendering, the illumination map for the object is
computed according to the current
lighting situation and then filtered by the precomputed kernels. The
illumination map is also used to derive the
incident illumination on the vertices which is distributed via the
vertex-to-vertex throughput factors to the other
vertices. The final image is obtained by combining the local and global
response. We demonstrate the performance
of our method for several models.
2003
Article
http://edoc.mpg.de/201866
urn:ISSN:0167-7055
Computer Graphics Forum, v.22, 195-205 (2003)
en
oai:edoc.mpg.de:2018682012-09-1987:934
Design of a Tone Mapping Operator for High Dynamic Range Images Based upon Psychophysical Evaluation and Preference Mapping
Drago, Frederic
Martens, William
Myszkowski, Karol
Chiba, Norishige
Rogowitz, Bernice
Pappas, Thrasyvoulos
A tone mapping algorithm for displaying high contrast scenes
was designed on the basis of the results of experimental
tests using human subjects.
Systematic
perceptual evaluation of several existing tone mapping
techniques revealed that the most ``natural'' appearance was
determined by the presence in the output image of detailed
scenery features often made visible by limiting contrast
and by properly reproducing brightness. Taking these results
into account, we developed a system to produce images close to
the ideal preference point for high dynamic range input image data.
Of the algorithms that we tested, only the Retinex algorithm was
capable of retrieving detailed scene features hidden in high luminance areas
while still preserving a good contrast level.
This paper presents changes made to Retinex algorithm for processing
high dynamic range images, and a further integration of the Retinex
with specialized tone mapping algorithms that enables the production
of images that appear as similar as possible to the viewer's
perception of actual scenes.
SPIE
2003
Conference-Paper
http://edoc.mpg.de/201868
Human Vision and Electronic Imaging VIII (HVEI-03), SPIE, 321-331 (2003)
en
oai:edoc.mpg.de:2018692012-09-1987:931
Fast Lightweight Suffix Array Construction and Checking
Burkhardt, Stefan
Kärkkäinen, Juha
Baeza-Yates, R.
Chávez, E.
Crochemore, M.
We describe an algorithm that, for any $v\in[2,n]$, constructs
the suffix array of a string of length $n$ in $\Oh{vn + n \log
n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the
input (the string) and the output (the suffix array). By setting
$v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using
$\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem
stated by Manzini and Ferragina [ESA\;'02] of whether there
exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time
algorithm. The key idea of the algorithm is to first sort a
sample of suffixes chosen using mathematical constructs called
difference covers. The algorithm is not only lightweight but also
fast in practice as demonstrated by experiments. Additionally,
we describe fast and lightweight suffix array checkers, i.e.,
algorithms that check the correctness of a suffix array.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201869
urn:ISSN:0302-9743
Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, Springer, 55-69 (2003)
en
oai:edoc.mpg.de:2018702012-09-1987:931
The factor algorithm for regular all-to-all communication on clusters of SMP nodes
Sanders, Peter
Träff, Jesper Larsson
Monien, Burkhard
Feldman, Rainer
Springer
2002
Conference-Paper
http://edoc.mpg.de/201870
urn:ISBN:3-450-67956-1
Proceedings of the 8th International Euro-Par Conference, Springer, 799-803 (2002)
en
oai:edoc.mpg.de:2018712012-09-1987:931
Random Arc Allocation and Applications to Disks, Drums and DRAMs
Sanders, Peter
Vöcking, Berthold
Penttonen, Martti
Meineche Schmidt, Erik
Springer
2002
Conference-Paper
http://edoc.mpg.de/201871
urn:ISBN:3-540-43866-1
Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory, Springer, 121-130 (2002)
en
oai:edoc.mpg.de:2018722012-09-1987:934
Accuracy of 3D Range Scanners by Measurement of the Slanted Edge Modulation Transfer Function
Goesele, Michael
Fuchs, Christian
Seidel, Hans-Peter
Rioux, Marc
Godin, Guy
Boulanger, Pierre
We estimate the accuracy of a 3D~range scanner in terms of its
spatial frequency response. We determine a scanner's modulation
transfer function (MTF) in order to measure its frequency response.
A slanted edge is scanned from which we derive a superresolution
edge profile. Its Fourier transform is compared to the Fourier
transform of an ideal edge in order to determine the MTF of the
device. This allows us to determine how well small details can be
acquired by the 3D~scanner. We report the results of several
measurements with two scanners under various conditions.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201872
4th International Conference on 3-D Digital Imaging and Modeling, IEEE, 37-44 (2003)
en
oai:edoc.mpg.de:2018742012-09-1987:931
The reliable algorithmic software challenge RASC : dedicated to Thomas Ottmann on the occassion of his 60th birthday
Mehlhorn, Kurt
Klein, Rolf
Six, Hans-Werner
Wegner, Lutz
Springer
2003
InBook
http://edoc.mpg.de/201874
urn:ISBN:3-540-00579-X
Computer Science in Perspective : essays dedicated to Thomas Ottmann, 255-263 (2003)
en
oai:edoc.mpg.de:2018752012-09-1987:933
Parallel "go with the winners algorithms" in Distributed Memory Models
Peinado, M.
Lengauer, Thomas
2003
Article
http://edoc.mpg.de/201875
Journal of Parallel and Distributed Processing, v.63, 801-814 (2003)
en
oai:edoc.mpg.de:2018762010-12-0387:936
Isoperimetric Inequalities and the Width parameters of graphs
Chandran, L. Sunil
Telikepalli, Kavitha
Subramanian, C. R.
Warnow, Tandy
Zhu, Binhai
Springer
2003
Conference-Paper
http://edoc.mpg.de/201876
urn:ISBN:3-540-40534-8
Computing and Combinatorics : 9th Annual International Conference, COCOON 2003, Springer, 385-393 (2003)
en
oai:edoc.mpg.de:2018772012-09-1987:933
A hazard based approach to dependence tests for bivariate censored models
Janssen, A.
Rahnenführer, Jörg
2003
Article
http://edoc.mpg.de/201877
Mathematical Methods in Statistics, v.11, 297-322 (2003)
en
oai:edoc.mpg.de:2018782012-09-1987:931
Tail bounds and expectations for random arc allocation and applications
Sanders, Peter
Vöcking, Berthold
2003
Article
http://edoc.mpg.de/201878
urn:ISSN:0963-5483
Combinatorics, Probability and Computing, v.12, 225-244 (2003)
en
oai:edoc.mpg.de:2018792010-12-0287:932
Orienting rewrite rules with the Knuth-Bendix order
Korovin, Konstantin
Voronkov, Andrei
We consider two decision problems related to the Knuth-Bendix order (KBO). The
first problem is \emph{orientability}: given a system of rewrite rules $R$,
does there exist an instance of KBO which orients every ground instance of
every rewrite rule in $R$. The second problem is whether a given instance of
KBO orients every ground instance of a given rewrite rule. This problem can
also be reformulated as the problem of solving a single ordering constraint for
the KBO. We prove that both problems can be
solved in the time polynomial in the size of the input.
The polynomial-time algorithm for orientability builds upon an algorithm for
solving systems of homogeneous linear inequalities over integers. We show that
the orientability problem is P-complete. The polynomial-time algorithm for
solving a single ordering constraint does not need to solve systems of linear
inequalities and can be run in time $O(n^2)$. Also we show that if a system is
orientable using a real-valued instance of KBO, then it is also orientable
using an integer-valued instance of KBO. Therefore, all our results hold both
for the integer-valued and the real-valued KBO.
2003
Article
http://edoc.mpg.de/201879
Information and Computation, v.183, 165-186 (2003)
en
oai:edoc.mpg.de:2018802010-12-0387:936
A compact linear program for testing optimality of perfect matchings
Ventura, Paolo
Eisenbrand, Friedrich
It is a longstanding open problem whether there exists a polynomial size
description of the perfect matching polytope. We give a partial answer to this
question by proving the following result. The polyhedron defined by the
constraints of the perfect matching polytope which are active at a given
perfect matching can be obtained as the projection of a compact polyhedron.
Thus there exists a compact linear program which is unbounded if and only if
the perfect matching is not optimal with respect to a given edge weight. This
result provides a simple reduction of the maximum weight perfect matching
problem to compact linear programming.
2003
Article
http://edoc.mpg.de/201880
urn:ISSN:0167-6377
Operations Research Letters, v.31, 429-434 (2003)
en
oai:edoc.mpg.de:2018812010-12-2087:937
Hardware-accelerated Autostereogram Rendering for Interactive 3D Visualization
Petz, Christoph
Goldluecke, Bastian
Magnor, Marcus
Woods, Andrew J.
Merritt, John O.
Benton, Stephen A.
Bolas, Mark T.
Single Image Random Dot Stereograms (SIRDS) are an attractive way of depicting
three-dimensional objects using conventional display technology. Once trained in
decoupling the eyes' convergence and focusing, autostereograms of this kind are
able to convey the three-dimensional impression of a scene. We present in this
work an algorithm that generates SIRDS at interactive frame rates on a
conventional PC. The presented system allows rotating a 3D geometry model and
observing the object from arbitrary positions in real-time. Subjective tests
show that the perception of a moving or rotating 3D scene presents no problem:
The gaze remains focused onto the object. In contrast to conventional SIRDS
algorithms, we render multiple pixels in a single step using a texture-based
approach, exploiting the parallel-processing architecture of modern graphics
hardware. A vertex program determines the parallax for each vertex of the
geometry model, and the graphics hardware's texture unit is used to render the
dot pattern. No data has to be transferred between main memory and the graphics
card for generating the autostereograms, leaving CPU capacity available for
other tasks. Frame rates of 25 fps are attained at a resolution of 1024x512
pixels on a standard PC using a consumer-grade nVidia GeForce4 graphics card,
demonstrating the real-time capability of the system.
SPIE
2003
Conference-Paper
http://edoc.mpg.de/201881
urn:ISBN:0-8194-4806-0
Stereoscopic Displays and Virtual Reality Systems X, SPIE, 359-366 (2003)
en
oai:edoc.mpg.de:2018822012-09-1987:933
Cost-effective screening for differentially expressed genes in microarray experiments based on normal mixtures
Rahnenführer, Jörg
Futschik, Andreas
2003
Article
http://edoc.mpg.de/201882
Austrian Journal of Statistics, v.32, 225-238 (2003)
en
oai:edoc.mpg.de:2018832010-12-0287:932
Deciding the Guarded Fragments by Resolution
de Nivelle, Hans
de Rijke, Maarten
We give resolution based decision procedures for both
the strictly guarded fragment and the loosely guarded
fragment of first-order logic. We prove that the
decision procedures are in 2EXPTIME, which is theoretically
optimal.
2003
Article
http://edoc.mpg.de/201883
urn:ISSN:0747-7171
Journal of Symbolic Computation, v.35, 21-58 (2003)
en
oai:edoc.mpg.de:2018852012-09-1987:931
Preemptive scheduling with rejection
Hoogeveen, Han
Skutella, Martin
Woeginger, Gerhard J.
We consider the problem of preemptively scheduling a set of $n$ jobs
on $m$ (identical, uniformly related, or unrelated) parallel
machines. The scheduler may reject a subset of the jobs and thereby
incur job-dependent penalties for each rejected job, and he must
construct a schedule for the remaining jobs so as to optimize the
preemptive makespan on the $m$ machines plus the sum of the
penalties of the jobs rejected.
We provide a complete classification of these scheduling problems
with respect to complexity and approximability. Our main results
are on the variant with an arbitrary number of unrelated machines.
This variant is \apx-hard, and we design a $1.58$-approximation
algorithm for it. All other considered variants are weakly
\np-hard, and we provide fully polynomial time approximation schemes
for them. Finally, we argue that our results for unrelated machines
can be carried over to the corresponding preemptive open shop
scheduling problem with rejection.
2003
Article
http://edoc.mpg.de/201885
urn:ISSN:0025-5610
Mathematical Programming, v.94, 361-374 (2003)
en
oai:edoc.mpg.de:2018862010-12-0287:932
Deciding Modal Logics through Relational Translations into GF2
de Nivelle, Hans
Demri, Stéphane
Areces, Carlos
Blackburn, Patrick
We provide a simple translation from the satisfiability problem for
regular grammar logics with converse into {GF2}, the intersection
of the guarded fragment and the 2-variable fragment of first-order
logic. The translation is theoretically interesting because
it translates modal logics with certain frame conditions into
first-order logic, without explicitly expressing the frame
conditions. Using the same method, one can show that other
modal logics can be naturally translated into {GF2},
including nominal tense logics and intuitionistic propositional
logic. In our view, the results in this paper provide strong
evidence that the natural first-order fragment corresponding
to modal logics, is {GF2}.
Loria
2003
Conference-Paper
http://edoc.mpg.de/201886
Proceedings of the 3rd Methods for Modalities Workshop, Loria, 15-30 (2003)
en
oai:edoc.mpg.de:2018892012-09-1987:931
The Safari Interface for Visualizing Time-dependent Volume Data Using Iso-surfaces and Contour Spectra
Kettner, Lutz
Rossignac, Jarek
Snoeyink, Jack
We describe a geometric basis for the visualization of time-varying
volume data of one or several variables as they occur in scientific
and engineering applications. We demonstrate a prototype
interface for gridded data, extending the contour spectrum interface of
Bajaj, Pascucci, and Schikore to higher dimensions and to topological
properties that are not decomposable. We also describe a data structure
for pentatope meshes that supports the computation of isosurfaces and their
properties.
2003
Article
http://edoc.mpg.de/201889
urn:ISSN:0925-7721
Computational Geometry - Theory and Applications, v.25, 97-116 (2003)
en
oai:edoc.mpg.de:2018902012-09-1987:931
Fast Bound-Consistency for the Global Cardinality Constraint
Katriel, Irit
Thiel, Sven
Rossi, Francesca
Springer
2003
Conference-Paper
http://edoc.mpg.de/201890
urn:ISBN:3-540-20202-1
Principles and Practice of Constraint Programming - CP 2003 : 9th International Conference, CP 2003, Springer, 437-451 (2003)
en
oai:edoc.mpg.de:2018912012-09-1987:931
Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation
Granados, Miguel
Hachenberger, Peter
Hert, Susan
Kettner, Lutz
Mehlhorn, Kurt
Seel, Michael
Di Battista, Giuseppe
Zwick, Uri
We describe a data structure for three-dimensional Nef complexes, algorithms
for boolean operations on them, and our implementation of data structure and
algorithms. Nef polyhedra were introduced by W. Nef in his seminal 1978 book on
polyhedra. They are the closure of half-spaces under boolean operations and can
represent non-manifold situations, open and closed boundaries, and mixed
dimensional complexes. Our focus lies on the generality of the data structure,
the completeness of the algorithms, and the exactness and efficiency of the
implementation. In particular, all degeneracies are handled.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201891
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 654-666 (2003)
en
oai:edoc.mpg.de:2018932010-12-0387:936
A faster algorithm for two-variable integer programming
Eisenbrand, Friedrich
Laue, Soeren
Ibaraki, Toshihide
Katoh, Naoki
Ono, Hirotaka
We show that a 2-variable integer program, defined by $m$ constraints
involving coefficients with at most $\varphi$ bits can be solved with
$O(m + \varphi)$ arithmetic operations on rational numbers of
size~$O(\varphi)$.
This result closes the gap between the running time of two-variable
integer programming with the sum of the running times of the
Euclidean algorithm on $\varphi$-bit integers and the problem of checking
feasibility of an integer point for $m$~constraints.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201893
urn:ISBN:3-540-20695-7
Algorithms and computation : 14th International Symposium, ISAAC 2003, Springer, 290-299 (2003)
en
oai:edoc.mpg.de:2018942010-12-0287:932
On Using Ground Joinable Equations in Equational Theorem Proving
Avenhaus, Jürgen
Hillenbrand, Thomas
Löchner, Bernd
When rewriting and completion techniques are used for equational
theorem proving, the axiom set is saturated with the aim to get a
rewrite system that is terminating and confluent on ground terms.
To reduce the computational effort it should (1) be powerful for
rewriting and (2) create not too many critical pairs. These problems
become especially important if some operators are associative and
commutative (\AC). We show in this paper how these two goals can be
reached to some extent by using ground joinable equations for
simplification purposes and omitting them from the generation of new
facts.
%
For the special case of \AC-operators we present a simple redundancy
criterion which is easy to implement, efficient, and effective in
practice, leading to significant speed-ups.
2003
Article
http://edoc.mpg.de/201894
urn:ISSN:0747-7171
Journal of Symbolic Computation, v.36, 217-233 (2003)
en
oai:edoc.mpg.de:2018952012-09-1987:933
Disease-associated variants in PYPAF1 and NOD2 result in similar alterations of conserved sequence
Albrecht, Mario
Lengauer, Thomas
Schreiber, Stefan
2003
Article
http://edoc.mpg.de/201895
Bioinformatics, v.19, 2171-2175 (2003)
en
oai:edoc.mpg.de:2018962012-09-1987:933
The unbinding of ATP from F1-ATPase
Antes, Iris
Wang, Hongyun
Chandler, David
Oster, George
2003
Article
http://edoc.mpg.de/201896
Biophysical Journal, v.85, 695-706 (2003)
en
oai:edoc.mpg.de:2018972010-12-0287:932
AC-compatible Knuth-Bendix Order
Korovin, Konstantin
Voronkov, Andrei
Baader, Franz
We introduce a family of AC-compatible Knuth-Bendix simplification orderings
which are AC-total on ground terms.
Our orderings preserve attractive features of
the original Knuth-Bendix orderings
such as polynomial algorithm for comparing terms; the orderings admit
computationally efficient approximations
like checking weights of terms;
and prefer light terms to heavy ones.
This makes them especially suited for automated deduction
where efficient treatment of orderings is desirable.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201897
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction, Springer, 47-59 (2003)
en
ResultSet_aAPDCFkFzdA_range_100-199