2020-10-22T09:33:17Zhttp://edoc.mpg.de/ac_p_oai.ploai:edoc.mpg.de:2017822012-09-1987:933
Conference-Paper
Towards cellular function through metabolite screening
English
Cambridge Healthtech Institute
Newton Upper Falls, USA
2003
2004-06-23
7
7
7
Princeton, New Jersey
2003-12-08
Proceedings of the 3rd Annual Conference on Metabolic Profiling: Pathways in Discovery
No
expertsonly
published
notspecified
P.
Talwar
Priti
T.
Lengauer
Thomas
C.
Wittmann
Christoph
V.
Mangadu
Vidya
E.
Heinzle
Elmar
C125673F004B2D7B-76BD83884DE933CCC1256EA600529A9D-Talwar2003
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2017852012-09-1987:931
Article
A theoretical and experimental study on the construction of suffix arrays in external memory
English
2002
2003-09-08
1
35
Algorithmica
32
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.
No
expertsonly
published
joureview
A.
Crauser
Andreas
P.
Ferragina
Paolo
0178-4617
C1256428004B93B8-1FE0191E40BE5BBBC12569FC0056CAD2-Crauser-Ferragina2001
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017872012-09-1987:933
InBook
Bioinformatikmethoden für die Optimierung antiviraler Kombinationstherapien
German
K. G. Saur Verlag
München, Germany
2003
2004-07-12
481
486
MPG Jahrbuch 2003
Max-Planck-Gesellschaft
No
expertsonly
published
notspecified
N.
Beerenwinkel
Niko
M.
Däumer
Martin
D.
Hoffmann
Daniel
R.
Kaiser
Rolf
J.
Selbig
Joachim
T.
Lengauer
Thomas
3-598-24930-6
C125673F004B2D7B-038EE4BFBD4D990BC1256D2E0033E846-BeerenwinkelLengauer2003d
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2017882012-09-1987:931
Conference-Paper
Heuristics for Semi-External Depth First Search on Directed Graphs
English
ACM
New York, USA
2002
2003-08-27
282
292
Winnipeg, Canada
2002-08-10
SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures
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.
No
expertsonly
published
notspecified
J.F.
Sibeyn
Jop F.
J.
Abello
James
U.
Meyer
Ulrich
1-58113-529-7
C1256428004B93B8-31A8B545C99A2D37C1256C1A003DE57B-SiAbMe02
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017892012-09-1987:931
Conference-Paper
Exact geometric computation
English
LEA
Athens, Greece
2002
2003-08-27
87
87
Athen, Griechenland
2001-09-20
HERCMA 2001 : proceedings of the 5th Hellenic-European Conference on Computer Mathematics and its Applications (HERCMA-01)
Hellenic-European Research on Computer Mathematics and its Applications
No
expertsonly
published
notspecified
K.
Mehlhorn
Kurt
E.A.
Lipitakis
Elias A.
960-85176-9-9
C1256428004B93B8-135A2711508AF90200256D110031DCD2-Mehlhorn02
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017902012-09-1987:933
Article
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
English
2002
2003-09-02
504
520
European Biophysics Jounal
31
No
expertsonly
published
joureview
I.
Antes
Iris
W.
Thiel
Walter
W.F.
Gunsteren van
Wilfred F.
0175-7571
C125673F004B2D7B-0B5AF0AAF156423AC1256CB80030E955-Antes2002a
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2017922012-09-1987:930
InBook
Classification and Focused Crawling for Semistructured Data
English
Springer
Berlin, Germany
2003
2004-07-06
145
157
2818
Intelligent Search on XML Data : Applications, Languages, Models, Implementations, and Benchmarks
Blanken, Henk; Grabs, Torsten; Schek, Hans-Jörg; Schenkel, Ralf; Weikum, Gerhard
No
expertsonly
published
notspecified
M.
Theobald
Martin
R.
Schenkel
Ralf
G.
Weikum
Gerhard
H.
Blanken
Henk
T.
Grabs
Torsten
H.-J.
Schek
Hans-Jörg
R.
Schenkel
Ralf
G.
Weikum
Gerhard
3-540-40768-5
C1256DBF005F876D-D2DC007A9E888EC5C1256DE400317FD9-TheobaldSW03
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2017932012-09-1987:931
Conference-Paper
External-Memory Breadth-First Search with Sublinear I/O
English
Springer
Berlin, Germany
2002
2003-09-08
723
735
Rome, Italy
2002-09-17
Algorithms - ESA 2002 : 10th Annual European Symposium
Lecture Notes in Computer Science
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.
No
expertsonly
published
notspecified
K.
Mehlhorn
Kurt
U.
Meyer
Ulrich
R.
Möhring
Rolf
R.
Raman
Rajeev
3-540-44180-8
C1256428004B93B8-A255EBD0F85324E4C1256C3D004FE88A-MehMey2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017942012-09-1987:934
Conference-Paper
Dual/Primal Mesh Optimization for Polygonized Implicit Surfaces
English
ACM
New York, USA
2002
2003-08-29
171
178
Saarbrücken, Germany
2002-06-17
Seventh ACM Symposium on Solid Modeling and Applications (SM-02)
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.
No
expertsonly
published
notspecified
Y.
Ohtake
Yutaka
A.
Belyaev
Alexander
K.
Lee
Kunwoo
N.M.
Patrikalakis
Nicho M.
1-58113-506-8
C125675300671F7B-DB14D84B5C9AA8EDC1256CB5005B3A8C-sm02ob
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2017952012-09-1987:934
Conference-Paper
A Framework for Dynamic Connectivity Meshes
English
ACM
New York, USA
2003
2004-07-12
49
55
Darmstadt, Germany
2003-03-31
OpenSG Symposium 2003
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9130&did=201795&ver=0
J.
Vorsatz
Jens
H.-P.
Seidel
Hans-Peter
D.
Reiners
D.
C125675300671F7B-7DB11C9D8C3B02F5C1256CED002FE17A-Vorsatz:2003:FDC
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2017962012-09-1987:931
Conference-Paper
Minimum Cost Flows Over Time without Intermediate Storage
English
ACM
New York, USA
2003
2004-08-02
66
75
Baltimore, USA
2003-01-12
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9131&did=201796&ver=0
L.
Fleischer
Lisa
M.
Skutella
Martin
0-89871-538-5
C1256428004B93B8-D67F80DC0F3DFECEC1256E200042012C-FleischerSkutella2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017982012-09-1987:934
Conference-Paper
Precomputed Radiance Transfer for Real-Time Rendering in Dynamic, Low-Frequency Lighting Environments
English
ACM
San Francisco, USA
2002
2003-08-29
527
536
San Antonio, USA
2002-07-21
Proceedings of ACM SIGGRAPH 2002 (SIGGRAPH-02)
acm Transactions on Graphics
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.
No
expertsonly
published
notspecified
P.-P.
Sloan
Peter-Pike
J.
Kautz
Jan
J.
Snyder
John
E.
Fiume
Eugene
1-58113-521-1
C125675300671F7B-648EA39D6E32FB00C1256BC10058387F-Sloan:PRT:2002
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2017992012-09-1987:934
Conference-Paper
Matrix Radiance Transfer
English
ACM
New York, USA
2003
2004-07-07
59
64
Monterey, USA
2003-04-27
ACM SIGGRAPH 2003 Symposium on Interactive 3D Graphics
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.
No
expertsonly
published
J.
Lehtinen
Jaakko
J.
Kautz
Jan
S.N.
Spencer
Stephen N.
1-58113-645-5
C125675300671F7B-59CA24CA5274C06FC1256CE9003A1D07-Lehtinen:2003:MRT
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018002012-09-1987:934
Article
Efficient Light Transport Using Precomputed Visibility
English
2003
2004-06-30
28
37
IEEE Computer Graphics and Applications
23
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.
No
expertsonly
published
joureview
K.
Daubert
Katja
W.
Heidrich
Wolfgang
J.
Kautz
Jan
J.-M.
Dischler
Jean-Michel
H.-P.
Seidel
Hans-Peter
C125675300671F7B-6D1DC36F06CF2CE9C1256C3000339FD4-Daubert:2003:ELT
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018012012-09-1987:931
Article
Better Filtering with Gapped q-Grams
English
2003
2004-06-15
51
70
Fundamenta Informaticae
56
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.
No
expertsonly
published
joureview
S.
Burkhardt
Stefan
J.
Kärkkäinen
Juha
0169-2968
C1256428004B93B8-97486D0D727E678AC1256D0900521D74-BurkhardtKarkkainen2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018022012-09-1987:934
Book
Advanced Global Illumination
English
A K Peters
Natick, USA
2003
No
expertsonly
340
published
P.
Dutré
Philip
P.
Bekaert
Philippe
K.
Bala
Kavita
C125675300671F7B-A34806641E0BA8BAC1256D0400510091-Dutre_2003book
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018032012-09-1987:934
Conference-Paper
Improved Hardware-Accelerated Visual Hull Rendering
English
Akademische Verlagsgesellschaft Aka
Berlin, Germany
2003
2004-08-03
151
158
Munich, Germany
2003-11-19
Vision, Modeling and Visualization 2003 (VMV-03) : proceedings
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=9132&did=201803&ver=0
M.
Li
Ming
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
T.
Ertl
Thomas
B.
Girod
Bernd
G.
Greiner
Günther
H.
Niemann
Heinrich
H.-P.
Seidel
Hans-Peter
E.
Steinbach
Eckehard
R.
Westermann
Rüdiger
3-89838-048-3
C125675300671F7B-401A8A42CE75880EC1256DDD005330D9-Li:2003:ImprovedHAVH
MPI für Informatik
Computer Graphics Group
MPI für Informatik
Graphics - Optics - Vision
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018042010-12-0387:937
Conference-Paper
Improved Hardware-Accelerated Visual Hull Rendering
English
Akademische Verlagsgesellschaft Aka
Berlin, Germany
2003
2004-08-03
151
158
Munich, Germany
2003-11-19
Vision, Modeling and Visualization 2003 (VMV-03) : proceedings
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=9133&did=201804&ver=0
M.
Li
Ming
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
T.
Ertl
Thomas
B.
Girod
Bernd
G.
Greiner
Günther
H.
Niemann
Heinrich
H.-P.
Seidel
Hans-Peter
E.
Steinbach
Eckehard
R.
Westermann
Rüdiger
3-89838-048-3
C125675300671F7B-401A8A42CE75880EC1256DDD005330D9-Li:2003:ImprovedHAVH
MPI für Informatik
Computer Graphics Group
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2018052010-12-0387:937
Article
Interactive Rendering of Translucent Objects
English
2003
2004-07-01
195
205
Computer Graphics Forum
22
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.
No
expertsonly
published
joureview
H.
Lensch
Hendrik
M.
Goesele
Michael
P.
Bekaert
Philippe
J.
Kautz
Jan
M.
Magnor
Marcus
J.
Lang
Jochen
H.-P.
Seidel
Hans-Peter
0167-7055
C1256BDE005F57A8-B6E1057E8746BD09C1256E14003D6492-Lensch:2003:IRT
MPI für Informatik
Graphics - Optics - Vision
MPI für Informatik
Computer Graphics Group
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2018062012-09-1987:931
Book
Algorithms for Memory Hierarchies
English
Springer
Berlin, Germany
2003
2625
No
expertsonly
428
published
U.
Meyer
Ulrich
P.
Sanders
Peter
J.F.
Sibeyn
Jop F.
3-540-00883-7
C1256428004B93B8-9B6D98DDAF2CC91FC1256D1F0036F1DF-MeySanSib2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018102010-12-0287:932
Conference-Paper
Citius altius fortius: Lessons learned from the Theorem Prover WALDMEISTER
English
Elsevier
Amsterdam, The Netherlands
2003
2004-06-22
1
13
Valencia, Spain
2003-06-12
Proceedings of the 4th International Workshop on First Order Theorem Proving, FTP'03
Electronic Notes in Theoretical Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9134&did=201810&ver=0
T.
Hillenbrand
Thomas
I.
Dahn
Ingo
L.
Vigneron
Laurent
C1256104005ECAFC-13192155732F5DD1C1256D32004620FA-Hillenbrand2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018112012-09-1987:931
Conference-Paper
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
English
IEEE
New York, USA
2003
2004-06-17
462
471
Cambridge, USA
2003-10-11
44th Annual Symposium on Foundations of Computer Science (FOCS-03)
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.
No
expertsonly
published
L.
Becchetti
Luca
S.
Leonardi
Stefano
A.
Marchetti-Spaccamela
Alberto
G.
Schäfer
Guido
T.
Vredeveld
Tjark
C1256428004B93B8-3CAAB1E7A5E7A119C1256E150031087F-Schäfer2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018122010-12-0287:932
Conference-Paper
A Principle for Incorporating Axioms into the First-Order Translation of Modal Formulae
English
Springer
Berlin, Germany
2003
2004-06-17
412
426
Miami, USA
2003-07-28
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction
Lecture Notes in Artificial Intelligence
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.
No
expertsonly
published
R.A.
Schmidt
Renate A.
U.
Hustadt
Ullrich
F.
Baader
Franz
3-540-40559-3
C1256104005ECAFC-7AECA712DA7DE0B2C1256D1A005CC61A-SchmidtHustadt03b
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018132012-09-1987:934
Conference-Paper
A Flexible and Versatile Studio for Multi-View Video Recording
English
Eurographics
Aire-la-Ville, Switzerland
2003
2004-08-03
9
16
Bath, UK
2003-07-10
Vision, Video and Graphics 2003
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.
No
expertsonly
published
C.
Theobalt
Christian
M.
Li
Ming
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
P.
Hall
Peter
P.
Willis
Philip
3-905673-54-1
C125675300671F7B-CCE30B9E5CABA5D6C1256D640040ABED-TheobaltVVG2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018142012-09-1987:933
Conference-Paper
Estimating effective drug combinations against drug-resistant mutants from genotypes
English
European AIDS Clinical Society
Paris, France
2003
2004-07-12
18
18
Luxembourg
2003-03-06
Proceedings of the 1st European HIV Drug Resistamce Workshop
HIV Medicine
No
expertsonly
published
N.
Beerenwinkel
Niko
M.
Däumer
Martin
R.
Kaiser
Rolf
H.
Walter
Hauke
K.
Korn
Klaus
D.
Hoffmann
Daniel
J.
Selbig
Joachim
T.
Lengauer
Thomas
C125673F004B2D7B-3A6131607909C01CC1256D260028CCD3-Beerenwinkel2003b
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018152012-09-1987:930
Article
Clustered Scheduling Algorithms for Mixed-Media Disk Workloads in a Multimedia Server
English
2003
2004-06-15
75
86
Cluster Computing
6
No
expertsonly
published
joureview
E.
Balafoutis
Elias
M.
Paterakis
Michael
P.
Triantafillou
Peter
G.
Nerjes
Guido
P.
Muth
Peter
G.
Weikum
Gerhard
1386-7857
C1256DBF005F876D-1851EC7400EFC55FC1256E14003E13A3-weikum2003d
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2018162012-09-1987:934
Conference-Paper
Neural Meshes: Statistical Learning based on Normals
English
IEEE
Los Alamitos, USA
2003
2004-07-12
404
408
Canmore, Alberta, Canada
2003-10-08
11th Pacific Conference on Computer Graphics and Applications (PG-03)
No
expertsonly
published
W.-K.
Jeong
Won-Ki
I.
Ivrissimtzis
Ioannis
H.-P.
Seidel
Hans-Peter
J.
Rokne
Jon
R.
Klein
Reinhard
W.
Wang
Wenping
0-7695-2028-6
C125675300671F7B-FB34C351DED7A5D8C1256E0B00697AC2-jis2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018172012-09-1987:931
Article
The complexity of economic equilibria for house allocation markets
English
2003
2004-06-15
219
223
Information Processing Letters
88
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9135&did=201817&ver=0
S. P.
Fekete
Sandor P.
M.
Skutella
Martin
G. J.
Woeginger
Gerhard J.
0020-0190
C1256428004B93B8-07975F653CB5FC7CC1256E1C0051D142-Skutella2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018182012-09-1987:934
Conference-Paper
A Multi-scale Approach to 3D Scattered Data Interpolation with Compactly Supported Basis Functions
English
IEEE
Los Alamitos, USA
2003
2004-06-30
153
161
Seoul, Korea
2003-05-12
Shape Modeling International 2003 (SMI 2003)
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.
No
expertsonly
published
notspecified
Y.
Ohtake
Yutaka
A.
Belyaev
Alexander
H.-P.
Seidel
Hans-Peter
M.-S.
Kim
Myung-Soo
C125675300671F7B-87B4CF5FB4E9EE9AC1256CB7006C0EC9-smi03obs
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018192012-09-1987:934
Conference-Paper
Exploiting Temporal Coherence in Ray Casted Walkthroughs
English
ACM
New York, USA
2003
2004-06-30
164
172
Budmerice, Slovakia
2003-04-24
Proceedings of the 19th Spring Conference on Computer Graphics 2003 (SCCG 03)
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.
No
expertsonly
published
V.
Havran
Vlastimil
J.
Bittner
Jiri
H.-P.
Seidel
Hans-Peter
K.I.
Joy
Kenneth I.
C125675300671F7B-8FBB3C9E989B6A44C1256CFE007D9073-Havran2003:SCCG
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018202012-09-1987:934
Conference-Paper
Construction and Animation of Anatomically Based Human Hand Models
English
ACM
New York, USA
2003
2004-07-07
98
109,368
San Diego, USA
2003-07-26
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SIGGRAPH-SCA-03)
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.
No
expertsonly
published
I.
Albrecht
Irene
J.
Haber
Jörg
H.-P.
Seidel
Hans-Peter
D.
Breen
Dave
M.
Lin
Ming
1-58113-659-5
C125675300671F7B-7BB1D8BD557CD39CC1256D2D0033E300-Albrecht:CAABHHM
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018212012-09-1987:934
InBook
MEDUSA - A Facial Modeling and Animation System
English
Gesellschaft für Wissenschaftliche Datenverarbeitung Göttingen
Göttingen, Germany
2003
2004-07-12
13
28
Forschung und wissenschaftliches Rechnen - Beiträge zum Heinz-Billing-Preis 2001
Plesser, Theo;Macho, Volker
No
expertsonly
published
notspecified
J.
Haber
Jörg
T.
Plesser
Theo
V.
Macho
Volker
0176-2516
C125675300671F7B-43C462A650480FE7C1256D9F002AF44F-Haber:Medusa
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018222010-12-0287:932
Conference-Paper
Universal variables in disconnection tableaux
English
Springer
Berlin, Germany
2003
2004-06-21
117
133
Rome, Italy
2003-09-09
Automated reasoning with analytical tableaux and related methods : International Conference, TABLEAUX 2003
Lecture Notes in Artificial Intelligence
No
expertsonly
published
R.
Letz
Reinhold
G.
Stenz
Gernot
M.
Cialdea Mayer
Marta
F.
Pirri
Fiora
3-540-40787-1
C1256104005ECAFC-7B50675EBAF47F08C1256EBA0047B1EA-LETZ03
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018232010-12-0287:932
Conference-Paper
The New WALDMEISTER Loop at Work
English
Springer
Berlin, Germany
2003
2004-06-23
317
321
Miami, Florida
2003-07-28
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction
Lecture Notes in Artificial Intelligence
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9137&did=201823&ver=0
J.-M.
Gaillourdet
Jean-Marie
T.
Hillenbrand
Thomas
B.
Löchner
Bernd
H.
Spies
Hendrik
F.
Baader
Franz
C1256104005ECAFC-F7AE319E928299C3C1256D01002DD440-GaillourdetHillenbrandLoechner2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018242012-09-1987:934
Conference-Paper
An Efficient Spatio-Temporal Architecture for Animation Rendering
English
ACM
New York, USA
2003
2004-07-12
106
117
Leuven, Belgium
2003-06-25
Rendering Techniques 2003 : 14th Eurographics Workshop on Rendering
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.
No
expertsonly
published
V.
Havran
Vlastimil
C.
Damez
Cyrille
K.
Myszkowski
Karol
H.-P.
Seidel
Hans-Peter
P.
Christensen
Per
D.
Cohen-Or
Daniel
1-58113-754-0
C125675300671F7B-375DE41ADBC27783C1256D2500414C13-Havran2003:EGSR
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018252012-09-1987:934
Article
Online Accelerated Rendering of Visual Hulls in Real Scenes
English
2003
2004-07-01
290
297
Journal of WSCG
11
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9138&did=201825&ver=0
M.
Li
Ming
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
1213-6972
C125675300671F7B-F966707B6258AAB2C1256C94003DE733-Ming:WSCG2003:OnlineRenderingVH
MPI für Informatik
Computer Graphics Group
MPI für Informatik
Graphics - Optics - Vision
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018262010-12-0387:937
Article
Online Accelerated Rendering of Visual Hulls in Real Scenes
English
2003
2004-07-01
290
297
Journal of WSCG
11
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9139&did=201826&ver=0
M.
Li
Ming
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
1213-6972
C125675300671F7B-F966707B6258AAB2C1256C94003DE733-Ming:WSCG2003:OnlineRenderingVH
MPI für Informatik
Computer Graphics Group
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2018272012-09-1987:931
Conference-Paper
Algorithms and Experiments for the Webgraph
English
Springer
Berlin, Germany
2003
2004-06-14
703
714
Budapest
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
No
expertsonly
published
L.
Laura
Luigi
S.
Leonardi
Stefano
S.
Millozzi
Stefano
U.
Meyer
Ulrich
J.F.
Sibeyn
Jop F.
G.
Di Battista
Giuseppe
U.
Zwick
Uri
0302-9743
C1256428004B93B8-9905E27D2ECB3E7BC1256E150036B925-LLMMS2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018282012-09-1987:934
Conference-Paper
Interactive Rendering of Translucent Deformable Objects
English
ACM
New York, USA
2003
2004-07-12
130
140
Leuven, Belgium
2003-06-25
Rendering Techniques 2003 : 14th Eurographics Workshop on Rendering
No
expertsonly
published
T.
Mertens
Tom
J.
Kautz
Jan
P.
Bekaert
Philippe
H.-P.
Seidel
Hans-Peter
F.
Van Reeth
Frank
P.
Christensen
Per
D.
Cohen-Or
Daniel
1727-3463
C125675300671F7B-53B6734B1ED834FAC1256E130014ABC1-Mertens:IRT:2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018292012-09-1987:931
Article
Reconciling simplicity and realism in parallel disk models
English
2002
2003-09-08
705
723
Parallel Computing
28
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.
No
expertsonly
published
joureview
P.
Sanders
Peter
0167-8191
C1256428004B93B8-B35A8F649B98C47FC1256CBE00620418-Sanders2002f
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018302010-12-0387:936
Article
Bounds on the Chvátal rank of Polytopes in the 0/1 Cube
English
2003
2004-07-01
245
261
Combinatorica
23
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$.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9140&did=201830&ver=0
F.
Eisenbrand
Friedrich
A. S.
Schulz
Andreas S.
1439-6912
C1256BDD00205AD6-AB10C772479876EAC1256CAA0035FA4A-ES2003
MPI für Informatik
Discrete Optimization Group
2010-12-03 14:48:31.809635
oai:edoc.mpg.de:2018312010-12-0387:936
Article
Primal Separation for 0/1 Polytopes
English
2003
2004-07-06
475
491
Mathematical Programming / A
95
\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.
No
expertsonly
published
joureview
F.
Eisenbrand
Friedrich
G.
Rinaldi
Giovanni
P.
Ventura
Paolo
0025-5610
C1256BDD00205AD6-873105CA3E3DF24BC1256CAA003307EF-ERV2003
MPI für Informatik
Discrete Optimization Group
2010-12-03 14:48:31.809635
oai:edoc.mpg.de:2018322012-09-1987:933
Article
Geno2pheno: estimating phenotypic drug resistance from HIV-1 genotypes
English
2003
2004-06-17
3850
3855
Nucleic Acids Research
31
No
expertsonly
published
joureview
N.
Beerenwinkel
Niko
M.
Däumer
Martin
M.
Oette
Mark
K.
Korn
Klaus
D.
Hoffmann
Daniel
R.
Kaiser
Rolf
T.
Lengauer
Thomas
J.
Selbig
Joachim
H.
Walter
Hauke
C125673F004B2D7B-5DC7A6E597F3C20AC1256D260025F206-Beerenwinkel2003a
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018332012-09-1987:934
Conference-Paper
Planned Sampling of Spatially Varying BRDFs
English
Blackwell
Oxford, Uk
2003
2004-07-05
473
482
Granada, Spain
2003-09-01
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference
No
expertsonly
published
H.P.A.
Lensch
Hendrik P. A.
J.
Lang
Jochen
A.M.
Sá
Asla M.
H.-P.
Seidel
Hans-Peter
P.
Brunet
Pere
D.W.
Fellner
Dieter W.
0167-7055
C125675300671F7B-CF0CF043F2C3CCF9C1256CFE0033246B-Lensch2003:PS
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018342012-09-1987:931
Conference-Paper
Approximating Energy Efficient Paths in Wireless Multi-hop Networks
English
Springer
Berlin, Germany
2003
2004-06-15
230
241
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
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$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9141&did=201834&ver=0
S.
Funke
Stefan
D.
Matijevic
Domagoj
P.
Sanders
Peter
G.
Di Battista
Giuseppe
U.
Zwick
Uri
3-540-20064-9
C1256428004B93B8-1EAC93284072E6C4C1256E150042DA25-Matijevic2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018352012-09-1987:931
Conference-Paper
On the Competitive Ratio for Online Facility Location
English
Springer
Berlin, Germany
2003
2004-06-15
637
652
Eindhoven, The Netherlands
2003-06-30
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9142&did=201835&ver=0
D.
Fotakis
Dimitris
J.C.M.
Baeten
Jos C.M.
J.K.
Lenstra
Jan Karel
J.
Parrow
Joachim
G.J.
Woeginger
Gerhard J.
3-540-40493-7
C1256428004B93B8-6A9C56FA859349F5C1256D030043742D-Fot03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018372012-09-1987:934
Conference-Paper
Shadow Volumes on Programmable Graphics Hardware
English
Blackwell
Oxford, UK
2003
2004-07-12
433
440
Granada, Spain
2003-09-01
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference
Computer Graphics Forum
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.
No
expertsonly
published
S.
Brabec
Stefan
H.-P.
Seidel
Hans-Peter
P.
Brunet
Pere
D.W.
Fellner
Dieter W.
0167-7055
C125675300671F7B-AFF5555AF0AF457CC1256D250049229E-Brabec2003:SPG
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018382012-09-1987:934
Conference-Paper
Feature Flow Fields
English
Eurographics
New York, USA
2003
2004-07-05
141
148
Grenoble, France
2003-05-26
Data Visualisation 2003 (VisSym-03) : Joint Eurographics / IEEE TCVG Symposium on Visualization
No
expertsonly
published
H.
Theisel
Holger
H.-P.
Seidel
Hans-Peter
G.-P.
Bonneau
Georges-Pierre
S.
Hahmann
Stefanie
C.
Hansen
Charles
S.N.
Spencer
Stephen N.
C125675300671F7B-2B84E27FB07E2F3CC1256CE90041DD37-Theisel2003a
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018392012-09-1987:934
Conference-Paper
Visualization of Volume Data with Quadratic Super Splines
English
IEEE
Los Alamitos, USA
2003
2004-08-03
393
400
Seattle, USA
2003-10-19
IEEE Visualization 2003 (VIS-03)
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9143&did=201839&ver=0
C.
Rössl
Christian
F.
Zeilfelder
Frank
G.
Nürnberger
Günther
H.-P.
Seidel
Hans-Peter
G.
Turk
Greg
J.
van Wijk
Jarke
R.
Moorhead
Robert
C125675300671F7B-667BB45D09712520C1256D41005222E9-RoesslZeilfelderNuernbergerSeidel2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018402012-09-1987:934
Conference-Paper
Reanimating Faces in Images and Video
English
Blackwell
Oxford, UK
2003
2004-07-12
641
650
Granada, Spain
2004-06-16
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference
Computer Graphics Forum
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.
No
expertsonly
published
V.
Blanz
Volker
C.
Basso
Curzio
T.
Vetter
Thomas
T.
Poggio
Tomaso
P.
Brunet
Pere
D.W.
Fellner
Dieter W.
0167-7055
C125675300671F7B-69430139A5B1F8D5C1256CFB0033E3C9-BlaBasVetPog2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018422012-09-1987:933
Conference-Paper
Efficient Clustering Methods for Tumor Classification with Microarrays
English
Springer
Berlin, Germany
2003
2004-06-21
670
679
Mannheim, Germany
2002-07-22
Proceedings of the 26th Annual Conference of the Gesellschaft für Klassifikation
Between Data Science and Applied Data Analysis
No
expertsonly
published
J.
Rahnenführer
Jörg
M.
Schader
Martin
W.
Gaul
Wolfgang
M.
Vichi
Maurizio
C125673F004B2D7B-45F2C5012898325EC1256D26003817A6-Rahnenf2003c
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018432012-09-1987:934
Conference-Paper
Dynamic Remeshing and Applications
English
ACM
New York, USA
2003
2004-06-30
167
175
Seattle, USA
2003-06-16
Proceedings: 8th ACM Symposium on Solid Modeling and Applications (SM-03)
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9146&did=201843&ver=0
http://edoc.mpg.de/get.epl?fid=9145&did=201843&ver=0
J.
Vorsatz
Jens
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
G.
Elber
Gershon
V.
Shapiro
Vadim
C125675300671F7B-690DFDA53D7BD4D8C1256CD4004EB2F0-Vorsatz:2003:DRA
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018442012-09-1987:931
Conference-Paper
Simple Linear Work Suffix Array Construction
English
Springer
Berlin, Germany
2003
2004-06-15
943
955
Eindhoven, The Netherlands
2003-06-30
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Lecture Notes in Computer Science
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.
No
expertsonly
published
J.
Kärkkäinen
Juha
P.
Sanders
Peter
J.C.M.
Baeten
Jos C.M.
J.K.
Lenstra
Jan Karel
J.
Parrow
Joachim
G.J.
Woeginger
Gerhard J.
3540404937
C1256428004B93B8-901BAE3BF9EE93A5C1256D090050B9C2-KarkkainenSanders2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018452012-09-1987:934
Conference-Paper
Reanimating the Dead: Reconstruction of Expressive Faces from Skull Data
English
ACM
New York, USA
2003
2004-07-07
554
561
San Diego, USA
2003-07-27
Proceedings of ACM SIGGRAPH 2003 (SIGGRAPH-03)
ACM Transactions on Graphics
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.
No
expertsonly
published
K.
Kähler
Kolja
J.
Haber
Jörg
H.-P.
Seidel
Hans-Peter
J.K.
Hodgins
Jessica K.
0730-0301
C125675300671F7B-53870ED9C6CEF425C1256CF3002C2808-Kaehler:2003:RD
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018462012-09-1987:934
Conference-Paper
Component-based Face Recognition with 3D Morphable Models
English
Springer
Berlin, Germany
2003
2004-06-30
27
34
Surrey, UK
2003-06-09
International Conference on Audio- and Video-Based Biometric Person Authentication (AVBPA-03)
Lecture Notes in Computer Science
No
expertsonly
published
J.
Huang
Jennifer
B.
Heisele
Bernd
V.
Blanz
Volker
J.
Kittler
Josef
M.S.
Nixon
Mark S.
C125675300671F7B-A097DD33EFD81779C1256CEF003A6D0D-HuaHeiBla03
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018472010-12-0387:937
Conference-Paper
Fast Hologram Synthesis for 3D Geometry Models using Graphics Hardware
English
SPIE
Bellingham, USA
2003
2004-07-01
266
275
Santa Clara, USA
2003-01-21
Practical Holography XVII and Holographic Materials IX
SPIE proceedings
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.
No
expertsonly
published
C.
Petz
Christoph
M.
Magnor
Marcus
T.H.
Jeong
Tung H.
S.H.
Stevenson
Sylvia H.
0-8194-4805-2
C1256BDE005F57A8-50751C2A7B545B83C1256CFB0041A1C1-Petz2003b
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
http://www.mpi-sb.mpg.de/~petz/holography.html
oai:edoc.mpg.de:2018482012-09-1987:934
Conference-Paper
Subdivision Rules for General Meshes
English
Nashboro Press
Brentwood, USA
2003
2004-06-30
229
238
St Malo, France
2002-06-27
Curve and Surface Fitting: Saint-Malo 2002
Proceedings of the 5th Conference on Curves and Surfaces
No
expertsonly
published
I.
Ivrissimtzis
Ioannis
K.
Shrivastava
Kanishka
H.-P.
Seidel
Hans-Peter
A.
Cohen
Albert
J.-L.
Merrien
Jean-Louis
L.L.
Schumaker
Larry L.
0-9728482-1-5
C125675300671F7B-A478D3CFC7926A43C1256CEF005BAE87-iss03
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018492012-09-1987:933
Conference-Paper
Statistical Inference for Clustering Microarrays
English
Springer
Berlin
2003
2004-06-21
323
332
Berkleley, USA
2001-03-19
Proceedings of the MSRI Workshop: Nonlinear Estimation and Classification
Lecture Notes in Statistics
No
expertsonly
published
J.
Rahnenführer
Jörg
D.D.
Denison
David D.
M.H.
Hansen
Mark H.
C.C.
Holmes
Christopher C.
B.
Mallick
Bani
B.
Yu
Bin
C125673F004B2D7B-7D1E17F38C770037C1256D260038F307-Rahnenf2001a
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018502012-09-1987:931
Conference-Paper
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers?
English
ACM
New York, USA
2003
2004-06-15
255
256
Baltimore, USA
2003-01-12
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
No
expertsonly
published
M.
Dhiflaoui
Marcel
S.
Funke
Stefan
C.
Kwappik
Carsten
K.
Mehlhorn
Kurt
M.
Seel
Michael
E.
Schömer
Elmar
R.
Schulte
Ralph
D.
Weber
Dennis
C1256428004B93B8-F01D6B673BC1A37AC1256CC200533255-dfkmsssw2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018512012-09-1987:931
Conference-Paper
Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location
English
Springer
Berlin, Germany
2003
2004-06-17
165
178
Ascona, Switzerland
2003-05-26
Experimental and efficient algorithms : Second International Workshop, WEA 2003
Lecture Notes in Computer Science
No
expertsonly
published
M.
Hoefer
Martin
K.
Jansen
Klaus
M.
Margraf
Marian
M.
Mastrolli
Monaldo
J.D.P.
Rolim
José D. P.
3-540-40205-5
C1256428004B93B8-0FF050BD4B94A840C1256EB60050AD58-Hoefer03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018522010-12-0287:932
Conference-Paper
Software Model Checking with Abstraction Refinement
English
Springer
Berlin, Germany
2003
2004-06-17
1
13
New York, NY (USA)
2003-01-09
Verification, model checking, and abstract interpretation : 4th International Conference, VMCAI 2003
Lecture Notes in Computer Science
No
expertsonly
published
A.
Podelski
Andreas
L.
Zuck
Lenore
P.
Attie
Paul
A.
Cortesi
Agostino
S.
Mukhopadhyay
Supratik
3-540-00348-7
C1256104005ECAFC-2595A3BEBA35C88BC1256D0A00307971-P-VMCAI03
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018532010-12-0287:932
Conference-Paper
Superposition modulo a Shostak Theory
English
Springer
Berlin, Germany
2003
2004-06-17
182
196
Miami, Florida
2003-07-28
Automated Deduction, CADE-19 : 19th International Conference on Automated Deduction
Lecture Notes in Artificial Intelligence
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9147&did=201853&ver=0
H.
Ganzinger
Harald
T.
Hillenbrand
Thomas
U.
Waldmann
Uwe
F.
Baader
Franz
3-540-40559-3
C1256104005ECAFC-4489C55BD13D7669C1256CFE005A7257-GanzingerHillenbrandWaldmann2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018542010-12-0387:937
Conference-Paper
Real-time, Free-viewpoint Video Rendering from Volumetric Geometry
English
SPIE
Bellingham, USA
2003
2004-07-07
1152
1158
Lugano, Switzerland
2003-07-08
Visual Communications and Image Processing 2003
SPIE proceedings
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.
No
expertsonly
published
B.
Goldluecke
Bastian
M.
Magnor
Marcus
T.
Ebrahimi
Touradj
T.
Sikora
Thomas
0-8194-5023-5
C1256BDE005F57A8-D11BE0D6CDAD64C2C1256CF000492F58-Goldluecke2003:FVR
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2018552012-09-1987:934
Conference-Paper
Efficient Rendering of Local Subsurface Scattering
English
IEEE
Los Alamitos, USA
2003
2004-07-12
51
58
Canmore, Canada
2003-10-08
11th Pacific Conference on Computer Graphics and Applications (PG-03)
No
expertsonly
published
T.
Mertens
Tom
J.
Kautz
Jan
P.
Bekaert
Philippe
H.-P.
Seidel
Hans-Peter
F.
Van Reeth
Frank
J.
Rokne
Jon
R.
Klein
Reinhard
W.
Wang
Wenping
C125675300671F7B-77F7AC6F8CCFC818C1256E130016C210-Mertens:ERL:2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018562010-12-0387:937
Conference-Paper
A Flexible and Versatile Studio for Synchronized Multi-view Video Recording
English
Eurographics
Aire-la-Ville, Switzerland
2003
2004-07-01
9
16
Bath, UK
2003-07-10
Vision, Video, and Graphics 2003
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.
No
expertsonly
published
C.
Theobalt
Christian
M.
Li
Ming
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
P.
Hall
Peter
P.
Willis
Philip
3-905673-54-1
C1256BDE005F57A8-30E4AD7EA98533D1C1256E14003CECFA-Theobalt:2003:FVS
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2018572012-09-1987:931
Conference-Paper
Space Efficient Hash Tables with Worst Case Constant Access Time
English
Springer
Berlin, Germany
2003
2004-06-11
271
282
Berlin, Germany
2003-02-27
Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003)
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9148&did=201857&ver=0
D.
Fotakis
Dimitris
R.
Pagh
Rasmus
P.
Sanders
Peter
P.G.
Spirakis
Paul G.
H.
Alt
Helmut
M.
Habib
Michel
3-540-00623-0
C1256428004B93B8-6A3318B88A19B993C1256CD800533F95-FPSS03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018582012-09-1987:934
Conference-Paper
Saddle Connectors - An Approach to Visualizing the Topological Skeleton of Complex 3D Vector Fields
English
IEEE
Los Alamitos, USA
2003
2004-08-03
225
232
Seattle, USA
2003-10-19
IEEE Visualization 2003 (VIS-03)
No
expertsonly
published
H.
Theisel
Holger
T.
Weinkauf
Tino
H.-C.
Hege
Hans-Christian
H.-P.
Seidel
Hans-Peter
G.
Turk
Greg
J.
van Wijk
Jarke
R.
Moorhead
Robert
C125675300671F7B-9844E96616128021C1256D3F0065F548-Theisel2003c
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018592012-09-1987:931
Conference-Paper
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property
English
Springer
Berlin, Germany
2003
2004-06-25
679
690
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
No
expertsonly
published
I.
Katriel
Irit
P.
Sanders
Peter
J.L.
Träff
Jesper Larsson
G.
Di Battista
Giuseppe
U.
Zwick
Uri
3540200649
C1256428004B93B8-497634CD780A862DC1256E1C006859C6-KatSanTra03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018602012-09-1987:933
InBook
Combinatorial Optimization Techniques for Three-Dimensional Arrangement Problems
English
Springer
Heidelberg
2003
2004-07-07
63
73
Mathematics - Key Technology for the Future
Willi Jäger; Hans-Joachim Krebs
No
expertsonly
published
notspecified
T.
Lengauer
Thomas
M.
Schäfer
M.
W.
Jäger
Willi
H.-J.
Krebs
Hans-Joachim
C125673F004B2D7B-EE6A14C206B55B8EC1256E1D003B700B-Lengauer2003b
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018612012-09-1987:931
InBook
Memory hierarchies - models and lower bounds
English
Springer
Berlin, Germany
2003
2004-06-17
1
10
2625
Algorithms for memory hierarchies
Meyer, Ulrich;Sanders, Peter;Sibeyn, Jop
No
expertsonly
published
notspecified
P.
Sanders
Peter
U.
Meyer
Ulrich
P.
Sanders
Peter
J.
Sibeyn
Jop
3-540-00883-7
C1256428004B93B8-1684EE73A63CE3FBC1256EB6004F403D-PS03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018622012-09-1987:934
Conference-Paper
Adaptive Logarithmic Mapping For Displaying High Contrast Scenes
English
Blackwell
Oxford, UK
2003
2004-07-12
419
426
Granada, Spain
2003-09-01
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference
Computer Graphics Forum
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.
No
expertsonly
published
F.
Drago
Frederic
K.
Myszkowski
Karol
T.
Annen
Thomas
N.
Chiba
Norishige
P.
Brunet
Pere
D.W.
Fellner
Dieter W.
C125675300671F7B-53A4B81D590A3EEAC1256CFD003CE441-Drago2003b
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018632012-09-1987:931
Conference-Paper
Nearest Neighbors Can Be Found Efficiently If the Dimension Is Small Relative to the Input Size
English
Springer
New York, USA
2003
2004-06-17
440
454
Siena, Italy
2003-01-08
Database Theory - ICDT 2003 : 9th International Conference
Lecture Notes in Computer Science
No
expertsonly
published
M.
Hagedoorn
Michiel
D.
Calvanese
Diego
M.
Lenzerini
Maurizio
R.
Motwani
Rajeev
3-540-00323-1
C1256428004B93B8-244F00DC9AEB81ADC1256CAF005D7C9F-Hagedoorn2003:nncbfe
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
The copyright for this distribution is held by Springer.
© Springer-Verlag
http://www.springer.de/comp/lncs/index.html
oai:edoc.mpg.de:2018642012-09-1987:931
Conference-Paper
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
English
Springer
Berlin, Germany
2003
2004-06-15
500
510
Bratislava
2003-08-25
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003
Lecture Notes in Computer Science
No
expertsonly
published
P.
Krysta
Piotr
P.
Sanders
Peter
B.
Vöcking
Berthold
B.
Rovan
Branislav
P.
Vojtáš
Peter
3540406719
C1256428004B93B8-572C4F06E92A32BDC1256E1D003E35D2-KSV03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018652012-09-1987:934
Conference-Paper
Characteristics of dual-sqrt(3) subdivision schemes
English
Nashboro Press
Brentwood, USA
2003
2004-06-30
119
128
St Malo, France
2002-06-27
Curve and Surface Fitting: Saint-Malo 2002
Proceedings of the 5th Conference on Curves and Surfaces
No
expertsonly
published
N.
Dodgson
Neil
I.
Ivrissimtzis
Ioannis
M.
Sabin
Malcolm
A.
Cohen
Albert
J.-L.
Merrien
Jean-Louis
L.L.
Schumaker
Larry L.
0-9728482-1-5
C125675300671F7B-222576678C757289C1256CED006362A1-dis03
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018662012-09-1987:934
Article
Interactive Rendering of Translucent Objects
English
2003
2004-07-01
195
205
Computer Graphics Forum
22
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.
No
expertsonly
published
joureview
H.P.A.
Lensch
Hendrik P. A.
M.
Goesele
Michael
P.
Bekaert
Philippe
J.
Kautz
Jan
M.
Magnor
Marcus
J.
Lang
Jochen
H.-P.
Seidel
Hans-Peter
0167-7055
C125675300671F7B-59DB2C094E5EAC08C1256D7C005E467E-Lensch:2003:IRO
MPI für Informatik
Computer Graphics Group
MPI für Informatik
Graphics - Optics - Vision
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018682012-09-1987:934
Conference-Paper
Design of a Tone Mapping Operator for High Dynamic Range Images Based upon Psychophysical Evaluation and Preference Mapping
English
SPIE
Bellinghan, USA
2003
2004-07-07
321
331
Santa Clara, USA
2003-01-21
Human Vision and Electronic Imaging VIII (HVEI-03)
SPIE proceedings
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.
No
expertsonly
published
F.
Drago
Frederic
W.
Martens
William
K.
Myszkowski
Karol
N.
Chiba
Norishige
B.
Rogowitz
Bernice
T.
Pappas
Thrasyvoulos
C125675300671F7B-AC62EE60325404E4C1256CE8006BA646-Myszkowski2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018692012-09-1987:931
Conference-Paper
Fast Lightweight Suffix Array Construction and Checking
English
Springer
Heidelberg, Germany
2003
2004-08-02
55
69
Morelia, Michoacán, Mexico
2003-06-25
Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9149&did=201869&ver=0
S.
Burkhardt
Stefan
J.
Kärkkäinen
Juha
R.
Baeza-Yates
R.
E.
Chávez
E.
M.
Crochemore
M.
0302-9743
C1256428004B93B8-3E2B1773D0314EDEC1256E8A002B0F6D-Burkhardt2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018702012-09-1987:931
Conference-Paper
The factor algorithm for regular all-to-all communication on clusters of SMP nodes
English
Springer
Berlin, Germany
2002
2003-08-28
799
803
Paderborn
2002-08-27
Proceedings of the 8th International Euro-Par Conference
Lecture Notes in Computer Science
No
expertsonly
published
notspecified
P.
Sanders
Peter
J.L.
Träff
Jesper Larsson
B.
Monien
Burkhard
R.
Feldman
Rainer
3-450-67956-1
C1256428004B93B8-CB53878DBD30EC6EC1256CBE0062DC16-Sanders2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018712012-09-1987:931
Conference-Paper
Random Arc Allocation and Applications to Disks, Drums and DRAMs
English
Springer
Berlin, Germany
2002
2003-08-29
121
130
Turku
2002-07-03
Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory
Lecture Notes in Computer Science
No
expertsonly
published
notspecified
P.
Sanders
Peter
B.
Vöcking
Berthold
M.
Penttonen
Martti
E.
Meineche Schmidt
Erik
3-540-43866-1
C1256428004B93B8-87AD39F4B8488430C1256CBE0063F98B-Sanders2002g
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018722012-09-1987:934
Conference-Paper
Accuracy of 3D Range Scanners by Measurement of the Slanted Edge Modulation Transfer Function
English
IEEE
Los Alamitos, USA
2003
2004-06-30
37
44
Banff, Canada
2003-10-06
4th International Conference on 3-D Digital Imaging and Modeling
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9150&did=201872&ver=0
M.
Goesele
Michael
C.
Fuchs
Christian
H.-P.
Seidel
Hans-Peter
M.
Rioux
Marc
G.
Godin
Guy
P.
Boulanger
Pierre
C125675300671F7B-1D1EDF899D4E8731C1256D2E0029DF07-Goesele:2003:A3R
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018742012-09-1987:931
InBook
The reliable algorithmic software challenge RASC : dedicated to Thomas Ottmann on the occassion of his 60th birthday
English
Springer
Berlin, Germany
2003
2004-06-28
255
263
2598
Computer Science in Perspective : essays dedicated to Thomas Ottmann
Klein, Rolf; Six, Hans-Werner; Wegner, Lutz
No
expertsonly
published
notspecified
K.
Mehlhorn
Kurt
R.
Klein
Rolf
H.-W.
Six
Hans-Werner
L.
Wegner
Lutz
3-540-00579-X
C1256428004B93B8-A185BAA82C068ABBC1256E1D0048A367-KM03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018752012-09-1987:933
Article
Parallel "go with the winners algorithms" in Distributed Memory Models
English
2003
2004-07-07
801
814
Journal of Parallel and Distributed Processing
63
No
expertsonly
published
joureview
M.
Peinado
M.
T.
Lengauer
Thomas
C125673F004B2D7B-2EB9261B028EFA7AC1256E150035511F-PeinadoLengauer2003a
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018762010-12-0387:936
Conference-Paper
Isoperimetric Inequalities and the Width parameters of graphs
English
Springer
Berlin, Germany
2003
2004-07-06
385
393
Big Sky, USA
2003-07-25
Computing and Combinatorics : 9th Annual International Conference, COCOON 2003
Lecture Notes in Computer Science
No
expertsonly
published
notspecified
L.S.
Chandran
L. Sunil
K.
Telikepalli
Kavitha
C.R.
Subramanian
C. R.
T.
Warnow
Tandy
B.
Zhu
Binhai
3-540-40534-8
C1256BDD00205AD6-3E8988A29BD13C55C1256E15003AAB22-Cocoon2003
MPI für Informatik
Discrete Optimization Group
2010-12-03 14:48:31.809635
oai:edoc.mpg.de:2018772012-09-1987:933
Article
A hazard based approach to dependence tests for bivariate censored models
English
2003
2004-06-23
297
322
Mathematical Methods in Statistics
11
No
expertsonly
published
joureview
A.
Janssen
A.
J.
Rahnenführer
Jörg
C125673F004B2D7B-C801A68A1003DDBDC1256CF00043DC24-Rahnenf2003b
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018782012-09-1987:931
Article
Tail bounds and expectations for random arc allocation and applications
English
2003
2004-06-15
225
244
Combinatorics, Probability and Computing
12
No
expertsonly
published
joureview
P.
Sanders
Peter
B.
Vöcking
Berthold
0963-5483
C1256428004B93B8-6F1F3105E951E1D4C1256E1C0069B7E0-SanVoe03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018792010-12-0287:932
Article
Orienting rewrite rules with the Knuth-Bendix order
English
2003
2004-06-23
165
186
Information and Computation
183
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.
No
expertsonly
published
joureview
K.
Korovin
Konstantin
A.
Voronkov
Andrei
C1256104005ECAFC-989A18913FFAD6B3C1256E24003DB3B9-KorovinVoronkov:IC:2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018802010-12-0387:936
Article
A compact linear program for testing optimality of perfect matchings
English
2003
2004-07-01
429
434
Operations Research Letters
31
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.
No
expertsonly
published
joureview
P.
Ventura
Paolo
F.
Eisenbrand
Friedrich
0167-6377
C1256BDD00205AD6-4A3D46B34DD76218C1256D09002D6698-VE2003
MPI für Informatik
Discrete Optimization Group
2010-12-03 14:48:31.809635
oai:edoc.mpg.de:2018812010-12-2087:937
Conference-Paper
Hardware-accelerated Autostereogram Rendering for Interactive 3D Visualization
English
SPIE
Bellingham, USA
2003
2004-07-01
359
366
Santa Clara, USA
2003-01-21
Stereoscopic Displays and Virtual Reality Systems X
SPIE proceedings
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.
No
expertsonly
published
notspecified
C.
Petz
Christoph
B.
Goldluecke
Bastian
M.
Magnor
Marcus
A. J.
Woods
Andrew J.
J. O.
Merritt
John O.
S. A.
Benton
Stephen A.
M. T.
Bolas
Mark T.
0-8194-4806-0
C1256BDE005F57A8-28C8A0ACB0550B24C1256CFB0040B77C-Petz2003
MPI für Informatik
Graphics - Optics - Vision
2010-12-20 11:11:06.444407
oai:edoc.mpg.de:2018822012-09-1987:933
Article
Cost-effective screening for differentially expressed genes in microarray experiments based on normal mixtures
English
2003
2004-06-21
225
238
Austrian Journal of Statistics
32
No
expertsonly
published
joureview
J.
Rahnenführer
Jörg
A.
Futschik
Andreas
C125673F004B2D7B-06720B3132039B75C1256E1500602EA3-Rahnenführer2003e
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018832010-12-0287:932
Article
Deciding the Guarded Fragments by Resolution
English
2003
2004-06-23
21
58
Journal of Symbolic Computation
35
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.
No
expertsonly
published
joureview
H.
de Nivelle
Hans
M.
de Rijke
Maarten
0747-7171
C1256104005ECAFC-444F28344A221540C1256D0900423679-deNivelle2003a
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018852012-09-1987:931
Article
Preemptive scheduling with rejection
English
2003
2004-06-15
361
374
Mathematical Programming
94
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9151&did=201885&ver=0
H.
Hoogeveen
Han
M.
Skutella
Martin
G.J.
Woeginger
Gerhard J.
0025-5610
C1256428004B93B8-0DAA99A7CBBA7B62C1256E20004335BB-HoogeveenSkutellaWoeginger2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018862010-12-0287:932
Conference-Paper
Deciding Modal Logics through Relational Translations into GF2
English
Loria
Nancy, France
2003
2004-06-21
15
30
Nancy, France
2003-09-22
Proceedings of the 3rd Methods for Modalities Workshop
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}.
No
expertsonly
published
H.
de Nivelle
Hans
S.
Demri
Stéphane
C.
Areces
Carlos
P.
Blackburn
Patrick
C1256104005ECAFC-B198890BD5638018C1256E270055D64F-deNivelleDemri2003c
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018892012-09-1987:931
Article
The Safari Interface for Visualizing Time-dependent Volume Data Using Iso-surfaces and Contour Spectra
English
2003
2004-06-15
97
116
Computational Geometry - Theory and Applications
25
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.
No
expertsonly
published
joureview
L.
Kettner
Lutz
J.
Rossignac
Jarek
J.
Snoeyink
Jack
0925-7721
C1256428004B93B8-3E3420DF169FD902C1256D0A005BBD78-Kettner2003Safari
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018902012-09-1987:931
Conference-Paper
Fast Bound-Consistency for the Global Cardinality Constraint
English
Springer
Berlin, Germany
2003
2004-06-17
437
451
Kinsale, Ireland
2003-09-29
Principles and Practice of Constraint Programming - CP 2003 : 9th International Conference, CP 2003
Lecture Notes in Computer Science
No
expertsonly
published
I.
Katriel
Irit
S.
Thiel
Sven
F.
Rossi
Francesca
3-540-20202-1
C1256428004B93B8-59ADBF4D9D0B5ACCC1256E1400562806-KT03:gcc
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018912012-09-1987:931
Conference-Paper
Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation
English
Springer
Berlin, Germany
2003
2004-06-15
654
666
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
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.
No
expertsonly
published
M.
Granados
Miguel
P.
Hachenberger
Peter
S.
Hert
Susan
L.
Kettner
Lutz
K.
Mehlhorn
Kurt
M.
Seel
Michael
G.
Di Battista
Giuseppe
U.
Zwick
Uri
C1256428004B93B8-D0F786CC6723EB72C1256E2F0050063D-ghhkms-bo3ds-03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018932010-12-0387:936
Conference-Paper
A faster algorithm for two-variable integer programming
English
Springer
Berlin, Germany
2003
2004-07-01
290
299
Kyoto, Japan
2003-12-15
Algorithms and computation : 14th International Symposium, ISAAC 2003
Lecture Notes in Computer Science
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.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=9152&did=201893&ver=0
F.
Eisenbrand
Friedrich
S.
Laue
Soeren
T.
Ibaraki
Toshihide
N.
Katoh
Naoki
H.
Ono
Hirotaka
3-540-20695-7
C1256BDD00205AD6-BEE4EA3106AD2FF7C1256E0C003B6F13-EisenbrandLaue2003
MPI für Informatik
Discrete Optimization Group
2010-12-03 14:48:31.809635
oai:edoc.mpg.de:2018942010-12-0287:932
Article
On Using Ground Joinable Equations in Equational Theorem Proving
English
2003
2004-06-23
217
233
Journal of Symbolic Computation
36
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.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9153&did=201894&ver=0
J.
Avenhaus
Jürgen
T.
Hillenbrand
Thomas
B.
Löchner
Bernd
0747-7171
C1256104005ECAFC-A129A5E170AD94F0C1256D01002C84B9-AvenhausHillenbrandLoechner2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018952012-09-1987:933
Article
Disease-associated variants in PYPAF1 and NOD2 result in similar alterations of conserved sequence
English
2003
2004-06-23
2171
2175
Bioinformatics
19
No
expertsonly
published
joureview
M.
Albrecht
Mario
T.
Lengauer
Thomas
S.
Schreiber
Stefan
C125673F004B2D7B-B552BF73F6D9D403C1256CD1005228AD-Albrecht2003c
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018962012-09-1987:933
Article
The unbinding of ATP from F1-ATPase
English
2003
2004-06-17
695
706
Biophysical Journal
85
No
expertsonly
published
joureview
I.
Antes
Iris
H.
Wang
Hongyun
D.
Chandler
David
G.
Oster
George
C125673F004B2D7B-B204BD3307B485E6C1256D26003E518A-Antes2003a
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2018972010-12-0287:932
Conference-Paper
AC-compatible Knuth-Bendix Order
English
Springer
Berlin, Germany
2003
2004-06-23
47
59
Miami, Florida
2003-05-14
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction
Lecture Notes in Computer Science
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.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9154&did=201897&ver=0
K.
Korovin
Konstantin
A.
Voronkov
Andrei
F.
Baader
Franz
C1256104005ECAFC-7B6594FD381CBD9AC1256D170068CDF9-KorovinVoronkov:CADE03:ACKBO
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
ResultSet_8r7OKnaaLHJ_range_100-199