Epsilon Geometry: Building Robust Algorithms from Imprecise Computations (2009)
Leonidas Guibast, David Salesinl, Jorge Stolfi
We describe a new general framework, called Epsilon Geometry, for coping with computational errors in geometric algorithms that arise from the use of finite precision arithmetic.
A Multi-Scale Method for the Re-Assembly of Fragmented Objects (2008)
Helena Cristina, Gama Leitão, Jorge Stolfi
We describe here an efficient algorithm for re-assembling one or more unknown objects that have been broken or torn into a large number Æ of irregular fragments—a problem that often arises in...
Digitalization and reconstruction of archaeological artifacts (2008)
Helena Cristina, Da Gama Leitão, Jorge Stolfi
Abstract. We describe an ongoing research project on efficient methods for reconstruction of objects from large collections of irregular fragments, such as ancient pottery, collapsed murals, etc.....
DIGITAL RECONSTRUCTION OF FRAGMENTED ARTIFACTS (2008)
Helena Cristina, G. Leitão, Jorge Stolfi
ts/Welcome.html Abstract (EN) ICHIM 04- Digital Culture & Heritage / Patrimoine & Culture Numérique We describe an ongoing research project on efficient methods for identification and...
Exact Representation and Operations on Spherical Maps (2008)
Marcus Vin, A. Andrade, Jorge Stolfi
Abstract. We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing apoint against...
Natural Language Vocabularies (2008)
Tomasz Kowaltowski, Cl'audio L. Lucchesi, Jorge Stolfi, Tomasz Kowaltowski, Cl'audio L. Lucchesi
O conte'udo do presente relat'orio 'e de 'unica responsabilidade do(s) autor(es). (The contents of this report are the sole responsibility of the author(s).)
Approximating Parametric Curves with Strip Trees using Affine Arithmetic (2008)
Luiz Henrique, De Figueiredo, Jorge Stolfi, Luiz Velho
Abstract. We show how to use affine arithmetic to represent a parametric curve with a strip tree. The requiredbounding rectangles for pieces of the curve are computed by exploiting the linear...
We propose the use of affine arithmetic in cell-mapping methods for the robust visualization of strange attractors and show that the resulting cellular approximations converge faster than those...
Abstract Finite Elements on Dyadic Grids with Applications (2008)
Maria Cristina Cunha, Anamaria Gomide, Denis J. Schiozer, Jorge Stolfi
A dyadic grid is a hierarchic mesh where a cell at level k is partitioned into two equal children at level k +1 by a hyperplane perpendicular to coordinate axis (k mod m). We consider here the finite...
We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation...
MULTIPHASE FLOW SIMULATION WITH DYNAMIC ADAPTIVE DYADIC GRIDS (2008)
Anamaria Gomide, Jorge Stolfi, Maria Cristina Cunha, Denis J. Schiozer
Abstract. We address the problem of efficient simulation of multiphase flow in porous media — in particular, flow in natural oil reservoirs under advanced exploitation regimes such as water...
An Exact Algorithm for Point Location on Spherical Maps (2008)
Marcus Vincius Andrade, A. Andrade, Wagner F. Barros, Jorge Stolfi
We describe here an exact, and hence robust, algorithm for point location on spherical maps (maps on the sphere composed by arcs of circles, not necessarily geodesic ones). The algorithm relies on an...
Draft Marcus, Marcus Vinicius, Alvim Andrade, Jo Luiz, Dihl Comba, Jorge Stolfi
Introduction Interval arithmetic (IA), also known as interval analysis, is a technique for numerical computation where each quantity is represented by an interval of floatingpoint numbers. Those...
Bases for Non-Homogeneous Polynomial C_k Splines on the Sphere (2007)
Anamaria Gomide, Jorge Stolfi, Where H
We investigate the use of non-homogeneous spherical polynomials for the approximation of functions defined on the sphere S^2. A spherical polynomial is the restriction to S^2 of a polynomial in the...
Dynamic Animation of Elastic Bodies (2007)
Rog' Erio Liesenfeld, Jorge Stolfi
. We describe an animation system that simulates the dynamics of viscoelastic bodies subject to equality and inequality constraints. The equations of motion are derived from Lagrange's equation,...
Dynamic Animation of Elastic Bodies (2007)
. We describe an animation system that simulates the dynamics of viscoelastic bodies subject to equality and inequality constraints. The equations of motion are derived from Lagrange's equation,...
Bases for Non-Homogeneous Polynomial C (2007)
Splines On The, Anamaria Gomide, Jorge Stolfi, Where H
. We investigate the use of non-homogeneous spherical polynomials for the approximation of functions defined on the sphere S 2 . A spherical polynomial is the restriction to S 2 of a polynomial in...
We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation...
Abstract. Affine arithmetic is a model for self-validated numerical computation that affine arithmetic keeps track of first-order correlations between computed and input quantities. We explain the...
Approximating Parametric Curves with Strip Trees using Affine Arithmetic (2007)
Luiz Henrique, De Figueiredo, Jorge Stolfi
Abstract. We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear...
We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation...
Exact Representation and Operations on Spherical Maps (2007)
Marcus Vin, A. Andrade, Jorge Stolfi
Abstract. We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point...
The Splitting Number and Skewness of (2007)
Theta Cm Candido, Candido F. Xavier, Mendonca Neto, Karl Schaffer, Erico F. Xavier, ...
The skewness of a graph G is the minimum number of edges that need to be deleted from G to produce a planar graph. The splitting number of a graph G is the minimum number of splitting steps needed to...
Visualization of Three-Dimensional Maps (2007)
A three-dimensional map is a partition of a 3D manifold into topological polyhedra. We consider here the problem of visualizing the topology of a three-dimensional map given only its combinatorial...
Digitization and Reconstruction of Archaeological Artifacts (2007)
Helena Cristina Da, Da Gama, Leit Ao, Jorge Stolfi, Each Defined
We describe an ongoing research project on efficient methods for reconstruction of objects from large collections of irregular fragments, such as ancient pottery, collapsed murals, etc.. Our solution...
Abstract. Affine arithmetic is a model for self-validated numerical computation that affine arithmetic keeps track of first-order correlations between computed and input quantities. We explain the...
Mutual information content of homologous DNA (2005)
Helena Cristina, G. Leitão, Luciana S. Pessôa, Jorge Stolfi, Niterói Rj Brasil, Niterói Rj Brasil
Mutual information content of homologous DNA sequences 553
Approximating parametric curves with strip trees using affine arithmetic (2002)
We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation...
Approximating parametric curves with strip trees using affine arithmetic (2002)
We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation...
Approximating Parametric Curves with Strip Trees using Affine Arithmetic (2002)
Luiz Henrique De, De Figueiredo, Jorge Stolfi, Luiz Velho
We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation...
Approximation Error Maps (2002)
Anamaria Gomide, A. Gomide, Jorge Stolfi
In order to analyze the accuracy of a fixed, finite-dimensional approximation space which is not uniform over its domain $\Omega$, we define the approximation error map, a description of how the...
Visualization of three-dimensional maps (2000)
A three-dimensional map is a partition of a 3D manifold into topological polyhedra. We consider the problem of visualizing the topology of a three-dimensional map given only its combinatorial...
A Multi-Scale Method for the Re-Assembly of Fragmented Objects (2000)
Helena Cristina, Gama Leitao, Jorge Stolfi
We describe here an efficient algorithm for re-assembling one or more unknown objects that have been broken or torn into a large number N of irregular fragments---a problem that often arises in...
Non-Homogeneous Polynomials C k Splines on the Sphere S n (2000)
Anamaria Gomide, Anamaria Gomide, Jorge Stolfi, Jorge Stol
A homogeneous spherical polynomial (HSP) is the restriction to the sphere S^{n-1} of a homogeneous polynomial on the cartesian coordinates x_1,x_2,..x_n of R^n. A homogeneous spherical spline is a...
The vertex deletion number and splitting number of a triangulation of Cn × Cm (1999)
Erico F. Xavier, Erico F. Xavier, Jorge Stolfi, Jorge Stolfi, Luerbio Faria, ...
The vertex deletion number OE(G) of a graph G is the minimum number of vertices that must be deleted from G to produce a planar graph. The splitting number oe(G) of G is the smallest number of vertex...
Information Contents of Fracture Lines (1999)
Reassembling unknown broken objects from a large collection of fragments is a common problem in archaeology and other elds. Computer tools have recently been developed, by the authors and by others,...
Automatic Visualization of 3D Complexes (1999)
A three-dimensional complex is a partition of a three-dimensional manifold into simple cells, faces, edges and vertices. We consider here the problem of automatically producing a \nice"...
The Vertex Deletion Number of Cn × Cm (1999)
Erico F. Xavier, Erico F. Xavier, ...
The vertex deletion number of a graph G is the smallest integer k 0 such that there is an planar induced subgraph of G obtained by the removal of k vertices of G. The Cn \Theta Cm graphs has...
Separation-Sensitive Collision Detection for Convex Objects (1999)
Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during...
Separation-Sensitive Collision Detection for Convex Objects (1998)
Erickson, Jeff, Guibas, Leonidas J., Stolfi, Jorge, Zhang, Li
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during...
Boris V. Cherkassky, Andrew V. Goldberg, Paul Martin, Jo~ao C. Setubal, Jorge Stolfi
This TR is a revision of the TR #97-127. The original TR was based on implementations written in different languages, different style, and using somewhat different low-level data structures. After...
Exact Algorithms for Circles on the Sphere (1998)
this paper, we are concerned with oriented circles on the sphere S
Exact Algorithms for Circles on the Sphere (1998)
A. Andrade, A. Andrade, Jorge Stolfi, Jorge Stolfi
We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point against a...
Automatic Assembly of Irregular Fragments (1998)
Helena Cristina, Helena Cristina, Jorge Stolfi, Jorge Stolfi
This report addresses following problem: given one or more unknown objects that have been broken or torn into a large number of irregular fragments, find the pairs of fragments that were adjacent in...
Dynamic Animation of Elastic Bodies (1998)
Rog Erio Liesenfeld, Jorge Stolfi
We describe an animation system that simulates the dynamics of viscoelastic bodies subject to equality and inequality constraints. The equations of motion are derived from Lagrange's equation,...
Exact representation and operations on spherical maps (1997)
We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point against a...
Ronald Van, Iwaarden Jorge Stolfi, Ronald Van Iwaarden, ...
We show that faster solutions to unconstrained global optimization problems can be obtained by combining previous accelerations techniques for interval branch-andbound methods with affine arithmetic,...
Self-Validated Numerical Methods and Applications (1997)
erical methods. We apologize to the reader for the length and verbosity of these notes but, like Pascal, 1 we didn't have the time to make them shorter. 1 "Je n'ai fait celle-ci plus...
Realistic Simulation of Viscoelastic Bodies (1997)
We describe an animation system that simulates the dynamics of viscoelastic bodies subject to equality and inequality constraints. We show how Lagrange's method can be used to derive the...
Exact Representation and Operations on Spherical Maps (1997)
Marcus Vin, A. Andrade, Jorge Stolfi
We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point against a...
Boris V. Cherkassky, Andrew V. Goldberg, Paul Martin, J.C. Setubal, Jo~ao C. Setubal, Jorge Stolfi
We conduct a computational study of unit capacity flow and bipartite matching algorithms. Our goal is to determine which variant of the push-relabel method is most efficient in practice and to...
Luiz Henrique, De Figueiredo, Ronald Van Iwaarden, Jorge Stolfi
We show that faster solutions to unconstrained global optimization problems can be obtained by combining previous accelerations techniques for interval branch-and-bound methods with affine...
Dynamic animation of elastic bodies (1996)
We describe an animation system that simulates the dynamics of viscoelastic bodies subject to equality and inequality constraints. The equations of motion are derived from Lagrange's equation, and...
Adaptive Enumeration of Implicit Surfaces with Affine Arithmetic (1996)
. We discuss adaptive enumeration and rendering methods for implicit surfaces, using octrees computed with affine arithmetic, a new tool for range analysis. Affine arithmetic is similar to standard...
Reconstruction of Fragmented Objects (1996)
Helena Cristina, Gama Leit, Jorge Stolfi
. We consider the problem of automatic reconstruction of fragmented objects, such as ancient vessels and documents, mural paintings, fossils, etc.. Our approach combines an original filtering...
Adaptive Enumeration of Implicit Surfaces with Affine Arithmetic (1996)
We discuss adaptive enumeration and rendering methods for implicit surfaces, using octrees computed with affine arithmetic, a new tool for range analysis. Affine arithmetic is similar to standard...
Automatic Visualization of Two-Dimensional Cellular Complexes (1996)
Rober Marcone Rosi, Rober Marcone Rosi, Jorge Stolfi, Jorge Stolfi
A two-dimensional cellular complex is a partition of a surface into a finite number of elements---faces (open disks), edges (open arcs), and vertices (points). The topology of a cellular complex...
Adaptive Enumeration of Implicit Surfaces with Affine Arithmetic (1995)
Luiz Henrique, Figueiredo Jorge Stolfi, Jorge Stolfi
We discuss adaptive enumeration and rendering methods for implicit surfaces, using octrees computed with affine arithmetic, a new tool for range analysis. Affine arithmetic is similar to standard...
Objects That Cannot Be Taken Apart With Two Hands (1993)
It has been conjectured that every configuration C of convex objects in 3-space with disjoint interiors can be taken apart by translation with two hands: that is, some proper subset of C can be...
Application of Finite Automata in Debugging Natural Language Vocabularies (1993)
Tomasz Kowaltowski, Cláudio L. Lucchesi, Cl'audio L. Lucchesi, Jorge Stolfi
Finite acyclic automata can be used as a very versatile tool in many applications involving natural language vocabularies. This work describes some experiments in "debugging"...
Minimization of Binary Automata (1993)
Tomasz Kowaltowski, Claudio L. Lucchesi, Tomasz Kowaltowski, Cl'audio L. Lucchesi, Cl'audio L. Lucchesi, Jorge Stolfi, ...
Finite automata used to represent large vocabularies of natural languages are quite sparse in the following sense: for the vast majority of states, almost all transitions lead to the rejecting state....
Affine Arithmetic and its Applications to Computer Graphics (1993)
We describe a new method for numeric computations, which we call affine arithmetic (AA). This model is similar to standard interval arithmetic, to the extent that it automatically keeps track of...
Minimization of Binary Automata (1993)
Tomasz Kowaltowski, Cláudio L. Lucchesi, Cl'audio L. Lucchesi, Jorge Stolfi
Finite automata used to represent large vocabularies of natural languages are quite sparse in the following sense: for the vast majority of states, almost all transitions lead to the rejecting state....
Affine arithmetic and its applications to computer graphics (1990)
We describe a new method for numeric computations, which we call affine arithmetic (AA). This model is similar to standard interval arithmetic, to the extent that it automatically keeps track of...
The ZZ-Buffer: A Simple and Efficient Rendering Algorithm with Reliable Antialiasing (1989)
The ZZ-buffer is a new rendering algorithm that is simple, effcient, and produces high-quality images. The algorithm correctly renders transparent surfaces, shadows with real penumbrae, and depth of...
Finite Automata and Efficient Lexicon Implementation (1988)
Tomasz Kowaltowski, Cláudio L. Lucchesi, Tomasz Kowaltowski, Cl'audio L. Lucchesi, Cl'audio L. Lucchesi, Jorge Stolfi, ...
We describe a general technique for the encoding of lexical functions --- such as lexical classification, gender and number marking, inflections and conjugations --- using minimized acyclic...
Pessimal Algorithms and Simplexity Analysis (1986)
: The twin disciplines of Pessimal Algorithm Design and Simplexity Analysis are introduced and illustrated by means of representative problems. 1. Introduction Consider the following problem: we are...
Pessimal Algorithms and Simplexity Analysis (1984)
Abstract: The twin disciplines of Pessimal Algorithm Design and Simplexity Analysis are introduced and illustrated by means of representative problems 1
Separation-Sensitive Collision Detection for Convex Objects
Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang
this paper, see http://www:uiuc:edu/ph/www/jee/pubs/kollide:html.