Mark De Berg, Siu-wing Cheng, Dan Halperin, Otfried Schwarzkopf
Abstract In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case...
Linear optimization queries* (2008)
Jiii Matouekt, Otfried Schwarzkopf
Let F be a set of n halfspaces in Ed (where the di-mension d ~ 3 is fixed) and c a d-component vector. We denote by LP(I’, c) the linear programming prob-lem of minimizing the function c. x over...
Separating an Object from its Cast Hee-Kap Ahn Mark de Berg y Prosenjit Bose z Siu-Wing (2008)
Dan Halperin, Jir Matousek, Otfried Schwarzkopf
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Hee-kap Ahn, Mark De Berg, Siu-wing Cheng, Dan Halperin, Otfried Schwarzkopf
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Hee-kap Ahn, Mark De Berg, Siu-wing Cheng, Dan Halperin, Otfried Schwarzkopf
We study geometric problems that arise in casting. Casting is a manufacturing process where liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid...
Otfried Schwarzkopf, Jules Vleugels
We define a set of arbitrarily-shaped objects in R d to be a low-density environment if any axis-parallel hypercube intersects only few objects of comparable or larger size. Generalizing and...
Otfried Schwarzkopf, Otfried Schwarzkopf, Pankaj K. Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal
y Jir'i Matousek z Otfried Schwarzkopf x We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and...
Reaching a Goal with Directional Uncertainty (2007)
Mark Berg, Mark Berg, Mark Overmars, Mark Overmars, Micha Sharir, Micha Sharir, ...
Overmars 1
Mark Overmars, Anil Rao, Otfried Schwarzkopf, Chantal Wentink
A familiar task in industrial applications is grasping an object to constrain its motions. When the external forces and torques acting on the object are uncertain or varying, form-closure grasps are...
Jii Matouek, Jii Matouek, Otfried Schwarzkopf, Otfried Schwarzkopf, Jif Matouek, Offtied Schwarzkopf
A Deterministic Algorithm for the Three-Dimensional
The Hyperlatex Markup Language (2007)
Hyperlatex is a package that allows you to prepare documents in Html, and, at the same time, to produce a neatly printed document from your input. Unlike
Mark De Berg, Olivier Devillers, Marc Van Kreveld, Otfried Schwarzkopf, Monique Teillaud
Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...
Otfried Schwarzkopf, Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Katrin Dobrindt, ...
Computing a single cell in the union of two
Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Marc Van Kreveld, Marc Van Kreveld, ...
apport de recherche
Separating an Object from its Cast (2002)
Ahn, Hee-Kap, De Berg, Mark, Bose, Prosenjit, Cheng, Siu-Wing, Halperin, Dan, Matousek, Jirí, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1998)
De Berg, Mark, Devillers, Olivier, Van Kreveld, Marc, Schwarzkopf, Otfried, Teillaud, Monique
Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...
Approximation of Convex Figures by Pairs of Rectangles (1998)
Schwarzkopf, Otfried, Fuchs, Ulrich, Rote, Günter, Welzl, Emo
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R....
Approximation of Convex Figures by Pairs of Rectangles (1998)
Schwarzkopf, Otfried, Fuchs, Ulrich, Rote, Günter, Welzl, Emo
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R....
Approximation of Convex Figures by Pairs of Rectangles (1998)
Schwarzkopf, Otfried, Fuchs, Ulrich, Rote, Günter, Welzl, Emo
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r subset of or equal to C subset of or equal to R....
Computing Many Faces in Arrangements of Lines and Segments. (1998)
Agarwal, Pankaj K., Matousek, Jirí, Schwarzkopf, Otfried
We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones....
Constructing Levels in Arrangements and Higher Order Voronoi Diagrams. (1998)
Agarwal, Pankaj K., De Berg, Mark, Matousek, Jirí, Schwarzkopf, Otfried
We give simple randomized incremental algorithms for computing the Amk-level in an arrangement of n lines in the plane or in an arrangement of n planes in $\Reals^3$. The expected running time of our...
Approximation of convex figures by pairs of rectangles (1998)
Otfried Schwarzkopf, Ulrich Fuchs, Emo Welzl
We consider the problem of approximating a convex �gure in the plane by a pair �r;R � of homothetic �that is, similar and parallel � rectangles with r � C � R. We show the existence of...
Constructing levels in arrangements and higher order Voronoi diagrams (1998)
Pankaj K. Agarwal, Mark De Berg, Otfried Schwarzkopf
We give simple randomized incremental algorithms for computing the k-level in an arrangement of n hyperplanes in two- and three-dimensional space. The expected running time of our algorithms is...
Computing the maximum overlap of two convex polygons under translations (1998)
M. De Berg, O. Devillers, M. Van Kreveld, O. Schwarzkopf, Mark Berg, Olivier Devillers, ...
Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct place-ments of Q with respect to P...
Approximation of convex figures by pairs of rectangles (1998)
Otfried Schwarzkopf, Ulrich Fuchs, Emo Welzl
We consider the problem of approximating a convex �gure in the plane by a pair �r;R � of homothetic �that is, similar and parallel � rectangles with r � C � R. We show the existence of...
Separating an Object from its Cast (1998)
Hee-kap Ahn, Mark De Berg, Siu-Wing Cheng, Jiri Matousek, Dan Halperin, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Computing many faces in arrangements of lines and segments (1998)
Pankaj K. Agarwal, Jiri Matousek, Otfried Schwarzkopf
We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones....
Range Searching in Low-Density Environments (1998)
Otfried Schwarzkopf, Jules Vleugels
this paper we argue that this property, which is in fact more general than the fatness condition, may be more suitable for the analysis of "real life" motion planning problems. The...
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 many faces in arrangements of lines and segments (1998)
Pankaj K. Agarwal, Otfried Schwarzkopf
Abstract. We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously...
Computing the Maximum Overlap of Two Convex Polygons Under Translations. (1998)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...
Computing the Maximum Overlap of Two Convex Polygons Under Translations. (1998)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...
Separating and Shattering Long Line Segments (1997)
Efrat, Alon, Schwarzkopf, Otfried
A line l is called a separator for a set S of objects in the plane if l avoids all the objects and partitions S into two non-empty subsets, lying on both sides of l. A set L of lines is said to...
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...
Otfried Schwarzkopf, Micha Sharir
Let \Sigma be a collection of n algebraic surface patches of
Separating an Object from its Cast (1997)
Hee-kap Ahn, Mark De Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jiri Matousek, ...
In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the...
Separating and Shattering Long Line Segments (1997)
Alon Efrat, Otfried Schwarzkopf
this paper we consider the problem of finding separators for a set of line-segments. Clearly this is sufficient to treat the case of general polygonal objects as well.
Separating and shattering long line segments (1997)
Alon Efrat, Otfried Schwarzkopf
A line l is called a separator for a set S of objects in the plane if l avoids all the objects and partitions S into two non-empty subsets, lying on both sides of l. A set L of lines is said to...
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...
Range Searching in Low-Density Environments (1996)
Schwarzkopf, Otfried, Vleugels, Jules
We define a set of arbitrarily-shaped objects in Imaged to be a low-density environment if any axis-parallel hypercube intersects only few objects of comparable or larger size. Generalizing and...
A Deterministic Algorithm for the Three-Dimensional Diameter Problem (1996)
Matousek, Jirí, Schwarzkopf, Otfried
We give a deterministic algorithm for computing the diameter of an n-point set in three dimensions with O(n logcn) running time, where c is a constant.
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
Let $P$ be a convex polygon in the plane with $n$ vertices and let $Q$ be a convex polygon with $m$ vertices. We prove that the maximum number of combinatorially distinct placements of $Q$ with...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
Let $P$ be a convex polygon in the plane with $n$ vertices and let $Q$ be a convex polygon with $m$ vertices. We prove that the maximum number of combinatorially distinct placements of $Q$ with...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
Let $P$ be a convex polygon in the plane with $n$ vertices and let $Q$ be a convex polygon with $m$ vertices. We prove that the maximum number of combinatorially distinct placements of $Q$ with...
The overlay of lower envelopes and its applications (1996)
Micha Sharir, Micha Sharir, Pankaj K. Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal, Otfried Schwarzkopf, ...
Sharir x Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F, G are the planar maps obtained by the xy-projections...
The Overlay of Lower Envelopes and its Applications (1996)
Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir
Let F and G be two collections of a total of n (possibly partially-defined) bivariate algebraic functions of constant maximum degree. The minimization diagrams of F , G are the planar maps obtained...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Marc Van Kreveld, Marc Van Kreveld, ...
Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...
The Overlay of Lower Envelopes and its Applications (1996)
Pankaj Agarwal, Pankaj K. Agarwal, Otfried Schwarzkopf, Otfried Schwarzkopf, Micha Sharir, Micha Sharir
Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F , G are the planar maps obtained by the xy-projections of the...
Cuttings and Applications (1995)
De Berg, Mark, Schwarzkopf, Otfried
We prove a general lemma on the existence of (1/r)-cuttings of geometric objects in E^d that satisfy certain properties. We use this lemma to construct (1/r)-cuttings of small size for arrangements...
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...
Cuttings and applications (1995)
P. Oi Bqid, Mark De Berg, Mark De Berg, Offtied Schwarzkopf, Mark Berg, Otfried Schwarzkopf, ...
We prove a general lemma on the existence of (1/r)-cuttings of geometric objects in I = that stisfy certain properties. We use this lemma to construct (1/r)-cuttings of (azymptotically) optimal size...
Piecewise linear paths among convex obstacles (1995)
Mark De Berg, Otfried Schwarzkopf
Let B be a set of n arbitrary (possibly intersecting) convex obstacles in R d. It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path...
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'...
Constructing Levels in Arrangements and Higher Order Voronoi Diagrams (1995)
Otfried Schwarzkopf, Pankaj K. Agarwal, Jiri Matousek, Pankaj K. Agarwal, Mark De Berg, Mark De Berg
We give simple randomized incremental algorithms for computing the k-level in an arrangement of n hyperplanes in two- and three-dimensional space. The expected running time of our algorithms is O(nk...
Immobilizing polygons against a wall (1995)
Mark Overmars, Anil Rao, Otfried Schwarzkopf, Chantal Wentink
A familiar task in industrial applications is grasping an object to constrain its motions. When the external forces and torques acting on the object are uncertain or varying, form-closure grasps are...
Reaching a goal with directional uncertainty (1994)
De Berg, Mark, Guibas, L., Halperin, D., Schwarzkopf, Otfried, Sharir, Micha, Teillaud, Monique
On lazy randomized incremental construction (1994)
Berg, Mark De, Dobrindt, Katrin, Schwarzkopf, Otfried
Disponible dans les fichiers attachés à ce document
Reaching a goal with directional uncertainty (1994)
De Berg, Mark, Guibas, Leonidas, Halperin, Dan, Schwarzkopf, Otfried, Sharir, Micha, Teillaud, Monique, ...
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
Reaching a goal with directional uncertainty (1994)
De Berg, Mark, Guibas, Leonidas, Halperin, Dan, Schwarzkopf, Otfried, Sharir, Micha, Teillaud, Monique, ...
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...
The Overlay ofLower Envelopes and its Applications (1994)
Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir
Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F, G are the planar maps obtained by the xy-projections of the...
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...
Reaching a Goal with Directional Uncertainty (1994)
Monique Teillaud, Mark De Berg, Mark De Berg, Leonidas Guibas, Leonidas Guibas, Dan Halperin, ...
: We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its...
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...
Computing Many Faces in Arrangements of Lines and Segments (1994)
Jiri Matousek, Pankaj K. Agarwal, Otfried Schwarzkopf, Otfried Schwarzkopf
We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones....
Approximation of Convex Figures by Pairs of Rectangles (1990)
Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, Emo Welzl
We consider the problem of approximating a convex figure in the plane by a pair (r, R) of homothetic (that is, similar and parallel) rectangles with r ` C ` R. We show the existence of such a pair...