Abstract Cost-Driven Octree Construction Schemes: An Experimental Study ∗ (2009)
Boris Aronov, Hervé Brönnimann
Many algorithmic problems are interesting to both theoreticians and practitioners, but in a different manner. While the theoreticians have traditionally focused on worst-case scenarios which is often...
Fast almost-linear-sized nets for boxes in the plane (2008)
Hervé Brönnimann, Jonathan Lenchner
Let B be any set of n axis-aligned boxes in R d, d ≥ 1. For any point p, we define the subset Bp of B as Bp = {B ∈ B: p ∈ B}. A box B in Bp is said to be stabbed by p. A subset N ⊆ B is a...
with the greedy flip algorithm (2008)
Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink
enumerating pointed pseudo-triangulations
Streaming self-scaling histograms with stability and optimality guarantees (2008)
Hervé Brönnimann, Joannès Vermorel
Abstract. Histograms provide discrete efficient representation of continuous data and can be constrained to fit various purposes. We provide the first offline sub-quadratic algorithm which applies to...
Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink
and enumerating pointed pseudo-triangulations
Practical and efficient geometric ε-approximations ∗ (2008)
Hüseyin Akcan, Hervé Brönnimann, Robert Marini
Abstract. We adapt an algorithm for computing a deterministic sample in a set system to compute εapproximations for certain geometric set systems. We give algorithms to evaluate the quality of our...
1 Introduction Cost-Optimal Quadtrees for Ray Shooting ∗ (2008)
Hervé Brönnimann, Marc Glisse, David R. Wood
Given a set S of objects, called a scene, the rayshooting problem asks, given a ray, what is the first
On the number of Euclidean ordinary points for lines in the plane (2008)
Jonathan Lenchner, Hervé Brönnimann
Given an arrangement of n not all coincident, not all parallel lines in the (projective or) Euclidean plane we have earlier shown that there must be at least (5n+6)/39 Euclidean ordinary points. We...
with the greedy flip algorithm (2008)
Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink
enumerating pseudo-triangulations
ABSTRACT GPS-Free Node Localization in Mobile Wireless Sensor Networks (2008)
Hüseyin Akcan, Hervé Brönnimann
An important problem in mobile ad-hoc wireless sensor networks is the localization of individual nodes, i.e., each node’s awareness of its position relative to the network. In this paper, we...
Towards Faster Linear-Sized Nets for Axis-Aligned Boxes in the Plane (2008)
Abstract. Let B be any set of n axis-aligned boxes in R d, d ≥ 1. We call a subset N ⊆ B a(1/c)-net for B if any p ∈ R d contained in more than n/c boxes of B must be contained in a box of N,...
Abstract A New Deterministic Data Aggregation Method For Wireless Sensor Networks (2008)
Hüseyin Akcan, Hervé Brönnimann
The processing capabilities of wireless sensor nodes enable to aggregate redundant data to limit total data flow over the network. The main property of a good aggregation algorithm is to extract the...
Chapter 4 Efficient Data-Reduction Methods for On-Line Association Rule Discovery (2008)
Hervé Brönnimann, Bin Chen, Manoranjan Dash, Yi Qiao, Peter Scheuermann
Classical data mining algorithms require one or more computationally intensive passes over the entire database and can be prohibitively slow. One effective method for dealing with this ever-worsening...
Abstract Space-Efficient Planar Convex Hull Algorithms 1 (2008)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Practical and efficient geometric ε-approximations ∗ (2008)
Hüseyin Akcan, Hervé Brönnimann, Robert Marini
Abstract. We adapt an algorithm for computing a deterministic sample in a set system to compute εapproximations for certain geometric set systems. We give algorithms to evaluate the quality of our...
Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink
and enumerating pointed pseudo-triangulations
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (2007)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Applications of the Generic Programming Paradigm in the Design of CGAL (2007)
Hervé Brönnimann, Lutz Kettner, Herv Br#nnimann, Stefan Schirra, Remco Veltkamp
We report on the use of the generic programming paradigm in the Computational Geometry Algorithms Library Cgal. The parameterization of the geometric algorithms in Cgal enhances flexibility and...
Hervé Brönnimann, Hervé Brönnimann, Olivier Devillers, Olivier Devillers, Thème Génie Logiciel, Projet Prisme, ...
The union of unit balls has quadratic complexity,
In-Place Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
Space-Efficient Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Cost-Optimal Quadtrees for Ray Shooting (2007)
Hervé Brönnimann, Marc Glisse, David R. Wood
this paper, the only objects we consider are simplices (points and segments inside the unit square [0; 1] in R , or points, segments and triangles inside the unit cube [0; 1] in R ). We denote the...
Lines tangent to four triangles in three-dimensional space (2007)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...
Lines tangent to four triangles in three-dimensional space (2007)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...
Putting your data structure on a diet (2007)
Hervé Brönnimann, Jyrki Katajainen, Pat Morin
Abstract. Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several...
Putting your data structure on a diet (2007)
Hervé Brönnimann, Jyrki Katajainen, Pat Morin
Abstract. Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several...
A Proposal to add Interval Arithmetic to the C++ Standard Library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
Interval arithmetic is a basic tool for certified mathematical computations, it is presented in many references. We describe here the formal proposal to include interval arithmetic in the C++...
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A Proposal to add Interval Arithmetic to the C++ Standard Library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
Interval arithmetic is a basic tool for certified mathematical computations, it is presented in many references. We describe here the formal proposal to include interval arithmetic in the C++...
The design of the Boost interval arithmetic library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We present the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. Interval computations are an essential tool for...
The design of the Boost interval arithmetic library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We present the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. Interval computations are an essential tool for...
Jyrki Katajainen, Gerth Stølting Brodal, Hervé Brönnimann, Manuel Macías Córdoba, Miguel Fiandor Gutiérrez, Kasper Egdø, ...
This volume contains the papers presented at the 6th STL Workshop which was
Minimum-cost coverage of point sets by disks (2006)
Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra (2006)
Hervé Brönnimann, Olivier Devillers, Vida Dujmović, Hazel Everett, Xavier Goaoc, Sylvain Lazard, ...
Abstract. Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the...
Deterministic Data Reduction in Sensor Networks Third (2006)
Hüseyin Akcan, Hervé Brönnimann
A wide range of mining and analysis problems involve extracting knowledge from count data. Such data typically arises from transactional data sets; here we consider the case where it arises from a...
Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm (2006)
Brönnimann, Hervé, Kettner, Lutz, Pocchiola, Michel, Snoeyink, Jack
This paper studies pseudo-triangulations for a given point set in the plane. Pseudo-triangulations have many properties of triangulations, and have more freedom since polygons with more than three...
Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm (2006)
Brönnimann, Hervé, Kettner, Lutz, Pocchiola, Michel, Snoeyink, Jack
This paper studies pseudo-triangulations for a given point set in the plane. Pseudo-triangulations have many properties of triangulations, and have more freedom since polygons with more than three...
A Proposal to add Interval Arithmetic to the C++ Standard Library (2006)
Pion, Sylvain, Brönnimann, Hervé, Melquiond, Guillaume
I will report on a recent effort by Guillaume Melquiond, Hervé Br"onnimann and myself to push forward a proposal to include interval arithmetic in the next C++ ISO standard. The goals of the...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Transversals to line segments in three-dimensional space (2005)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...
Brönnimann, Hervé, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
A Proposal to add Interval Arithmetic to the C++ Standard Library (2005)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
Interval arithmetic is a basic tool for certified mathematical computations, it is presented in many references. We describe here the formal proposal to include interval arithmetic in the C++...
Line tangents to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in R^3. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and at most 156...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...
Transversals to line segments in three-dimensional space (2005)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Transversals to line segments in three-dimensional space (2005)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...
Computational Geometry 34 (2006) 159--181 (2005)
Www Elsevier Com, Boris Aronov, Hervé Brönnimann, Allen Y. Chang, Yi-jen Chiang
The ray shooting problem arises in many different contexts and is a bottleneck of ray tracing in computer graphics. Unfortunately, theoretical solutions to the problem are not very practical, while...
Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm (2005)
Brönnimann, Hervé, Kettner, Lutz, Pocchiola, Michel, Snoeyink, Jack, Demetrescu, Camil, Tamassia, Roberto, ...
This paper studies (pointed, or minimal) pseudo-triangulations for a given point set in the plane. Pseudo-triangulations have many properties of triangulations, and have more freedom since polygons...
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...
Cost-optimal trees for ray shooting, in (2004)
Abstract. Predicting and optimizing the performance of ray shooting is a very important problem in computer graphics due to the severe computational demands of ray tracing and other applications,...
Www Elsevier Com, Boris Aronov, Hervé Brönnimann, Allen Y. Chang, Yi-jen Chiang
Given a scene consisting of objects, ray shooting queries answer with the first object encountered by a given ray, and are used in ray tracing and radiosity for rendering photo-realistic images in...
Towards in-place geometric algorithms and data structures (2004)
Hervé Brönnimann, Timothy M. Chan, Eric Y. Chen
For many geometric problems, there are efficient algorithms that use surprisingly very little extra space other than the given array holding the input. For many geometric query problems, there are...
Transversals to Line Segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...
The number of transversals to line segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n>2 arbitrary line segments in R^3 admit 0, 1, ..., n or...
Transversals to Line Segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...
Transversals to Line Segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...
The Boost Interval Arithmetic Library (2003)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We report on the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. The design of the library is unique in that it...
The Boost Interval Arithmetic Library (2003)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We report on the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. The design of the library is unique in that it...
Towards In-Place Geometric Algorithms and Data Structures (2003)
Hervé Brönnimann, Timothy M. Chan, Eric Y. Chen
For many geometric problems, there are ecient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are...
Cost prediction for ray shooting (2002)
Boris Aronov, Hervé Brönnimann, Allen Y. Chang, Yi-jen Chiang
The ray shooting problem arises in many different contexts. For example, solving it efficiently would remove a bottleneck when images are ray-traced in computer graphics. Unfortunately, theoretical...
Optimal in-place planar convex hull algorithms (2002)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Godfried Toussaint
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (2001)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss floating-point filters as a means of restricting the precision needed for arithmetic operations while still computing the exact result. We show that interval techniques can be...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (2001)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss floating-point filters as a means of restricting the precision needed for arithmetic operations while still computing the exact result. We show that interval techniques can be...
The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin (1999)
Brönnimann, Hervé, Devillers, Olivier
We provide a lower bound construction showing that the union of unit balls in R3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.
The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin (1999)
Brönnimann, Hervé, Devillers, Olivier
We provide a lower bound construction showing that the union of unit balls in R3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.
The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin (1999)
Brönnimann, Hervé, Devillers, Olivier
We provide a lower bound construction showing that the union of unit balls in R3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.
Sign Determination in Residue Number Systems (1999)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We...
Sign Determination in Residue Number Systems (1999)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We...
Geometric Approximation Algorithms and Randomized Algorithms for Planar Arrangements (1999)
Prof Micha Sharir, Hervé Brönnimann, Bernard Chazelle, Ken Clarkson, Alon Efrat, Jeff Erickson, ...
by
Sign Determination in Residue Number Systems (1999)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Sign determination in residue number systems (1999)
Hervé Brönnimann, Ioannis Z. Emiris, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (1998)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (1998)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding...
Applications of the Generic Programming Paradigm in the Design of CGAL (1998)
Hervé Brönnimann, Lutz Kettner, Stefan Schirra, Remco Veltkamp
We report on the use of the generic programming paradigm in the computational geometry algorithms library cgal. The parameterization of the geometric algorithms in cgal enhances flexibility and...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (1998)
Hervé Brönnimann, Herv Br#nnimann, Sylvain Pion, Christoph Burnikel
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Efficient Exact Evaluation of Signs of Determinants (1997)
Brönnimann, Hervé, Yvinec, Mariette
This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with integer entries. The first one is a method based on the Gram-Schmidt...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Efficient Exact Evaluation of Signs of Determinants (1997)
Brönnimann, Hervé, Yvinec, Mariette
This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with integer entries. The first one is a method based on the Gram-Schmidt...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Efficient Exact Evaluation of Signs of Determinants (1997)
Brönnimann, Hervé, Yvinec, Mariette
This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with integer entries. The first one is a method based on the Gram-Schmidt...
Exact rounding for geometric constructions (1997)
Brönnimann, Hervé, Pion, Sylvain
Exact rounding is provided for elementary floating-point arithmetic operations (e.g. in the IEEE standard). Many authors have felt that it should be provided for other operations, in particular for...
Exact rounding for geometric constructions (1997)
Brönnimann, Hervé, Pion, Sylvain
Exact rounding is provided for elementary floating-point arithmetic operations (e.g. in the IEEE standard). Many authors have felt that it should be provided for other operations, in particular for...
Computing exact geometric predicates using modular arithmetic with single precision (1997)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Computing exact geometric predicates using modular arithmetic with single precision (1997)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Exact Rounding for Geometric Constructions (1997)
Hervé Brönnimann, Sylvain Pion
Exact rounding is provided for elementary floating-point arithmetic operations (e.g. in the IEEE standard). Many authors have felt that it should be provided for other operations, in particular for...
Exact Modular Arithmetic With Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Ioannis Z. Emiris, Victor Y. Pan, ...
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
A Complete Analysis of Clarkson's Algorithm for Safe Determinant Evaluation (1996)
Brönnimann, Hervé, Yvinec, Mariette
In this paper, we give a complete and self-contained analysis of Clarkson's algorithm that performs safe and efficient determinant evaluation of an $n\times n$ matrix with integer coefficients that...
A Complete Analysis of Clarkson's Algorithm for Safe Determinant Evaluation (1996)
Brönnimann, Hervé, Yvinec, Mariette
In this paper, we give a complete and self-contained analysis of Clarkson's algorithm that performs safe and efficient determinant evaluation of an $n\times n$ matrix with integer coefficients that...
A Complete Analysis of Clarkson's Algorithm for Safe Determinant Evaluation (1996)
Brönnimann, Hervé, Yvinec, Mariette
In this paper, we give a complete and self-contained analysis of Clarkson's algorithm that performs safe and efficient determinant evaluation of an $n\times n$ matrix with integer coefficients that...
A complete analysis of Clarkson's algorithm for safe determinant evaluation (1996)
Hervé Brönnimann, Hervé Brönnimann, Mariette Yvinec, Mariette Yvinec, Thème Génie Logiciel, Projet Prisme, ...
In this paper, we give a complete and self-contained analysis of Clarkson's algorithm that performs safe and efficient determinant evaluation of an n × n matrix with integer...
A complete analysis of Clarkson's algorithm for safe determinant evaluation (1996)
Hervé Brönnimann, Mariette Yvinec, Projet Prisme
In this paper, we give a complete and self-contained analysis of Clarkson's algorithm that performs safe and efficient determinant evaluation of an n × n matrix with integer...
Almost Optimal Set Covers in Finite VC-Dimension (1995)
Hervé Brönnimann, Michael T. Goodrich
We give a deterministic polynomial time method for finding a set cover in a set system (X
Almost Optimal Set Covers in Finite VC-Dimension (1995)
Hervé Brönnimann, Michael T. Goodrich
We give a deterministic polynomial time method for finding a set cover in a set system (X, R) of VC-dimension d such that the size of our cover is at most a factor of O(d log(dc)) from the optimal...
Product Range Spaces, Sensitive Sampling, and Derandomization (1993)
Hervé Brönnimann, Bernard Chazelle, Jirí Matousek
We introduce the concept of a sensitive epsilon-approximation, and use it to derive a more efficient algorithm for computing epsilon-nets. We define and investigate product range spaces, for which we...
How Hard Is Halfspace Range Searching? (1993)
Hervé Brönnimann, Bernard Chazelle, János Pach, J Anos Pach
We investigate the complexity of halfspace range searching: Given n points in d- space, build a data structure that allows us to determine efficiently how many points lie in a query halfspace. We...