Computing a Single Cell in the Overlay of two Simple Polygons? (2008)
Mark Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf A
This note combines the lazy randomized incremental construction scheme with the technique of \connectivity acceleration " to obtain an O(n(log? n) 2) time randomized algorithm to compute a...
Otfried Schwarzkopf, Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Katrin Dobrindt, ...
Computing a single cell in the union of two
Computing a Single Cell in the Overlay of two Simple Polygons (1998)
Mark De Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf
Introduction The arrangement of n line segments in the plane can be computed using a randomized incremental algorithm in expected time O(n log n + A), where A is the number of intersection points of...
Computing a Single Cell in the Overlay of two Simple Polygons (1997)
De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried
This note combines the lazy randomized incremental construction scheme with the technique of “connectivity acceleration” to obtain an O(n(log* n)2) time randomized algorithm to compute a single...
Computing a single cell in the union of two simple polygons (1997)
Berg, Mark De, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried
This note combines the lazy randomized incremental construction scheme with the technique of ``connectivity acceleration'' to obtain an O( (n log*n)^2) time randomized algorithm to compute a single...
Computing a single cell in the union of two simple polygons (1997)
Berg, Mark De, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried
This note combines the lazy randomized incremental construction scheme with the technique of ``connectivity acceleration'' to obtain an O( (n log*n)^2) time randomized algorithm to compute a single...
Computing a Single Cell in the Union of two Simple Polygons (1995)
De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried
This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme \cite{bds-lric-94} to maintain structures with `non...
Computing a Single Cell in the Union of two Simple Polygons (1995)
De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried
This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme \cite{bds-lric-94} to maintain structures with `non...
Computing a Single Cell in the Union of two Simple Polygons (1995)
De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried
This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme \cite{bds-lric-94} to maintain structures with `non...
Computing a Single Cell in the Union of Two Simple Polygons (1995)
Otfried Schwarzkopf, Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Katrin Dobrindt, ...
This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme [dBDS94] to maintain structures with `non local'...
On lazy randomized incremental construction (1994)
Berg, Mark De, Dobrindt, Katrin, Schwarzkopf, Otfried
Disponible dans les fichiers attachés à ce document
On lazy randomized incremental construction (1994)
Berg, Mark De, Dobrindt, Katrin, Schwarzkopf, Otfried
Disponible dans les fichiers attachés à ce document
On lazy randomized incremental construction (1994)
Mark De Berg, Katrin Dobrindt, Otfried Schwarzkopf
We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, these lazy randomized incremental algorithms are suited for computing structures...
On lazy randomized incremental construction (1994)
Mark Berg, Mark Berg, Mark Berg, Katrin Dobrindt, Katrin Dobrindt, Katrin Dobrindt, ...
We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, these lazy randomized incremental algorithms are suited for computing structures...
Katrin Dobrindt, Messieurs Yves, Mikhael Atallah Examinateur, Madame Mariette, Yvinec Examinateur
. Computational geometry aims at designing efficient algorithms for geometric problems. This branch of theoretical computer science has made enormous progress in the last fifteen years. In this...
On Lazy Randomized Incremental Construction (1994)
Mark De Berg, Mark De Berg, Katrin Dobrindt, Katrin Dobrindt, Otfried Schwarzkopf, Otfried Schwarzkopf, ...
: We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, these lazy randomized incremental algorithms are suited for computing...
A Complete and efficient algorithm for the intersection of a general ans a convex polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
On-line randomized construction of the upper envelope of triangles and surface patches in R3 (1993)
Boissonnat, Jean-Daniel, Dobrindt, Katrin
In this paper we describe an on-line randomized algorithm for computing the upper envelope (i.e. poinwise maximum) of a set of n triangles in three dimensions. The main new feature of this algorithm...
A Complete and efficient algorithm for the intersection of a general ans a convex polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
On-line randomized construction of the upper envelope of triangles and surface patches in R3 (1993)
Boissonnat, Jean-Daniel, Dobrindt, Katrin
In this paper we describe an on-line randomized algorithm for computing the upper envelope (i.e. poinwise maximum) of a set of n triangles in three dimensions. The main new feature of this algorithm...
A Complete and efficient algorithm for the intersection of a general ans a convex polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
On-line randomized construction of the upper envelope of triangles and surface patches in R3 (1993)
Boissonnat, Jean-Daniel, Dobrindt, Katrin
In this paper we describe an on-line randomized algorithm for computing the upper envelope (i.e. poinwise maximum) of a set of n triangles in three dimensions. The main new feature of this algorithm...
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Katrin Dobrindt, Katrin Dobrindt, Kurt Mehlhorn, Kurt Mehlhorn, Mariette Yvinec, Mariette Yvinec, ...
: A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette, Sack, Jörg-Rüdiger, Santoro, Nicola, ...
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
Un polyedre est tout ensemble qui peut etre obtenu a partir de demi-espaces par un nombre fini d{'}operations de complement et d{'}intersection. Nous proposons ici un algorithme complet et efficace...