The Complexity of the Outer Face in Arrangements of Random Segments ∗ (2009)
Noga Alon, Dan Halperin, Oren Nechushtan, Micha Sharir
We investigate the complexity of the outer face in arrangements of line segments of a fixed length ℓ in the plane, drawn uniformly at random within a square. We derive upper bounds on the expected...
Planning corridors among obstacles has arisen as a central problem in game design. Instead of devising a one-dimensional motion path for a moving entity, it is possible to let it move in a corridor,...
We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R 3. Our implementation is complete in the sense that it does not assume general...
Dan Halperin, Lydia E. Kavraki, Jean-claude Latombe, Rajeev Motwani, Christian Shelton, ...
Abstract. In recent years an effort has been made to supplement traditional methods for drug discovery by computer-assisted “structure-based design. ” The structure-based approach involves (among...
of Flexible Ligands \Lambda (2008)
Dan Halperin, Lydia Kavraki, Jean-claude Latombe, Rajeev Motwani, Christian Shelton, Suresh Venkatasubramanian
1 Introduction Most existing pharmaceutical drugs were found either by chance observation or by screening a large number of natural and synthetic substances [7]. In recent years there has been a...
Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space ∗ (2008)
Dan Halperin, Ophir Setter, Micha Sharir
We present a general framework for computing two-dimensional Voronoi diagrams of different site classes under various distance functions. The computation of the diagrams employs the Cgal software for...
Paul W. Finn, Dan Halperin, Lydia E. Kavraki, Jean-claude Latombe, Rajeev Motwani
2, Christian Shelton 2, Suresh Venkatasubramanian 2 1
Planning corridors among obstacles has arisen as a central problem in game design. Instead of devising a one-dimensional motion path for a moving entity, it is possible to let it move in a corridor,...
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...
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 We show how to compute and maintain the two-dimensional arrangement on a quadric that is induced by...
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 We study the performance in practice of various point-location algorithms implemented in cgal,...
Itay Lotan, Fabian Schwarzer, Jean-claude Latombe, Dan Halperin
The kinematic chain is a ubiquitous and extensively studied representation in robotics as well as a useful model for studying the motion of biological macro-molecules. Both fields stand to benefit...
Abstract The 2-Center Problem with Obstacles* (2008)
Dan Halperin, Micha Sharir, Ken Goldberg
Given a set S of n points in the plane and a set O of pairwise disjoint simple polygons with a total of m edges, we wish to find two congruent disks of small-est radius whose union covers S and whose...
Abstract On the Exact Maximum Complexity of Minkowski Sums of Convex (2008)
Efi Fogel, Dan Halperin, Christophe Weibel
We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in R3. In particular, we prove that the maximum number of facets of the Minkowski sum of two convex...
Given a collection B of balls in three-dimensional space, each having a radius of at least 1, we present an approximation scheme that constructs a collection Kε of unit balls that approximate B,...
Transforming a geometric algorithm into an effective computer program is a difficult task. This transformation is particularly made hard by the basic assumptions of most theoretical geometric...
An intersection-sensitive algorithm for snap rounding (2008)
Mark Berg, Dan Halperin, Mark Overmars
Snap rounding is a method for converting arbitrary-precision arrangements of segments into fixed-precision representation. We present an algorithm for snap rounding with running time O((n + I)log n),...
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...
We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R 3. Our implementation is complete in the sense that it does not assume general...
An intersection-sensitive algorithm for snap rounding (2008)
Mark Berg, Dan Halperin, Mark Overmars
Snap rounding is a method for converting arbitrary-precision arrangements of segments into fixed-precision representation. We present an algorithm for snap rounding with running time O((n + I)logn),...
Daniel Cohen-or, Gadi Fibich, Dan Halperin, Eyal Zadicario
Computing the visibility of out-door scenes is often much harder than of in-door scenes. A typical urban scene, for example, is densely occluded, and it is effective to precompute its visibility...
We introduce a new type of diagram called the VV (c)-diagram (the Visibility–Voronoi diagram for clearance c), which is a hybrid between the visibility graph and the Voronoi diagram of polygons in...
An intersection-sensitive algorithm for snap rounding (2008)
Mark Berg, Dan Halperin, Mark Overmars
Snap rounding is a method for converting arbitrary-precision arrangements of segments into fixed-precision representation. We present an algorithm for snap rounding with running time O((n + I)log n),...
www.cs.uu.nl The Visibility–Voronoi Complex and Its Applications ∗ (2008)
Ron Wein, Dan Halperin, Ron Wein, Dan Halperin
We introduce a new type of diagram called the VV (c)-diagram (the Visibility–Voronoi diagram for clearance c), which is a hybrid between the visibility graph and the Voronoi diagram of polygons in...
Improved Maintenance of Molecular Surfaces Using Dynamic Graph Connectivity ⋆ (2008)
Abstract. We present recent developments in efficiently maintaining the boundary and surface area of protein molecules as they undergo conformational changes. As the method that we devised keeps a...
The motion-planning problem, involving the computation of a collision-free path for a moving entity amidst obstacles, is a central problem in fields like Robotics and Game Design. In this paper we...
Efficient Generation of k-Directional Assembly Sequences (2008)
Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir
Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...
MolAxis: a server for identification of channels in macromolecules (2008)
Yaffe, Eitan, Fishelovitch, Dan, Wolfson, Haim J., Halperin, Dan, Nussinov, Ruth
MolAxis is a freely available, easy-to-use web server for identification of channels that connect buried cavities to the outside of macromolecules and for transmembrane (TM) channels in proteins....
CGAL - Smallest Enclosing Circle with Polygonal Obstacles ( Min_circle_obstacles_2 ) (2007)
. Given a set S of points in the plane and a set P of polygons (obstacles), we wish to nd a disc of radius r that covers S and whose center is not inside one of the polygons in P , as well as to...
Dan Halperin, Lydia Kavraki, Jean-claude Latombe
INTRODUCTION Robotics is concerned with the generation of computer-controlled motions of physical objects in a wide variety of settings. Because physical objects define spatial distributions in...
Geometric Manipulation of F (2007)
Proc Of, Paul W. Finn, Dan Halperin, Lydia E. Kavraki, Rajeev Motwani, Christian Shelton, ...
. In recent years an effort has been made to supplement traditional methods for drug discovery by computer-assisted "structure-based design." The structure-based approach involves (among...
Efficient Generation of (2007)
Proc Th, Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir
Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...
Efficient Generation of (2007)
To Appear, Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir
Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...
Dan Halperin, Lydia Kavraki, Jean-claude Latombe
INTRODUCTION Robotics is concerned with the generation of computer-controlled motions of physical objects in a wide variety of settings. Because physical objects define spatial distributions in...
) Dan Halperin Department of Computer Science Tel-Aviv University Tel-Aviv 69978, ISRAEL Abstract The increasing use of robot simulation systems has raised the need for a full kinematic treatment for...
Dan Halperin, Lydia Kavraki, Jean-claude Latombe
INTRODUCTION Robotics is concerned with the generation of computer-controlled motions of physical objects in a wide variety of settings. Because physical objects define spatial distributions in...
E#cient Maintenance and Self-Collision Testing for Kinematic Chains (2007)
Itay Lotan, Fabian Schwarzer, Dan Halperin, Jean-claude Latombe
The kinematic chain is a ubiquitous and extensively studied representation in robotics as well as a useful model for studying the motion of biological macro-molecules. Both fields stand to benefit...
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...
Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink
This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...
Reaching a Goal with Directional Uncertainty (2007)
Mark Berg, Mark Berg, Mark Overmars, Mark Overmars, Micha Sharir, Micha Sharir, ...
Overmars 1
Abstract. It is known that a scene consisting of k convex polyhedra of total complexity n has at most O(n 4
Pankaj K. Agarwal, Eyal Flato, Dan Halperin
Several algorithms for computing the Minkowski sum of two polygons in the plane begin by decomposing each polygon into convex subpolygons. We examine different methods for decomposing polygons by...
Herve Bronnimann Yi-Jen Chiang (2007)
Abstract It is known that a scene consisting of k convex polyhedra of total complexity n has at most O((n 2
Leonidas J. Guibas, Dan Halperin, Hirohisa Hirukawa, Jean-claude Latombe, Randall H. Wilson
We study the following problem: given a collection of polyhedral parts in 3D, determine whether there is a subset of the parts that can be moved as a rigid body by an infinitesimal translation and...
Pankaj K. Agarwal, Eyal Flato, Dan Halperin
Several algorithms for computing the Minkowski sum of two polygons in the plane begin by decomposing each polygon into convex subpolygons. We examine dierent methods for decomposing polygons by their...
Prediction and simulation of motion in pairs of transmembrane {alpha}-helices (2007)
Enosh, Angela, Fleishman, Sarel J., Ben-Tal, Nir, Halperin, Dan
Motivation: Motion in transmembrane (TM) proteins plays an essential role in a variety of biological phenomena. Thus, developing an automated method for predicting and simulating motion in this class...
Sweeping and maintaining two-dimensional arrangements on surfaces: A first step (2007)
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein
We introduce a general framework for processing a set of curves defined on a continuous two-dimensional parametric surface, while sweeping the parameter space. We can handle planes, cylinders,...
Sweeping and maintaining two-dimensional arrangements on surfaces: A first step (2007)
Eric Berberich, Efi Fogel, Dan Halperin, Ron Wein
We introduce a general framework for processing a set of curves defined on a continuous two-dimensional parametric surface, while sweeping the parameter space. A major goal of our work is to maximize...
On the exact maximum complexity of Minkowski sums of convex polyhedra (2007)
Efi Fogel, Dan Halperin, Christophe Weibel
We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in R3. In particular, we prove that the maximum number of facets of the Minkowski sum of two convex...
Sweeping and maintaining two-dimensional arrangements on surfaces: A first step (2007)
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein
Abstract. We introduce a general framework for sweeping a set of curves embedded on a two-dimensional parametric surface. We can handle planes, cylinders, spheres, tori, and surfaces homeomorphic to...
On the exact maximum complexity of Minkowski sums of convex polyhedra (2007)
Efi Fogel, Dan Halperin, Christophe Weibel
We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in R 3. In particular, we prove that the maximum number of facets of the Minkowski sum of two convex...
Sweeping and maintaining two-dimensional arrangements on surfaces: A first step (2007)
Berberich, Eric, Fogel, Efi, Halperin, Dan, Mehlhorn, Kurt, Wein, Ron
Sweeping and maintaining two-dimensional arrangements on quadrics (2007)
Berberich, Eric, Fogel, Efi, Halperin, Dan, Mehlhorn, Kurt, Wein, Ron
Sweeping and maintaining two-dimensional arrangements on surfaces (2007)
Berberich, Eric, Fogel, Efi, Halperin, Dan, Wein, Ron
We introduce a general framework for processing a set of curves defined on a continuous two-dimensional parametric surface, while sweeping the parameter space. A major goal of our work is to maximize...
An experimental study of point location in general planar arrangements (2006)
We study the performance in practice of various point-location algorithms implemented in Cgal, including a newly devised Landmarks algorithm. Among the other algorithms studied are: a naïve...
Planning near-optimal corridors amidst obstacles (2006)
Abstract: Planning corridors among obstacles has arisen as a central problem in game design. Instead of devising a one-dimensional motion path for a moving entity, it is possible to let it move in a...
Exact and efficient construction of Minkowski sums of convex polyhedra with applications (2006)
We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R 3. Our implementation is complete in the sense that it does not assume general...
An experimental study of point location in general planar arrangements (2006)
We study the performance in practice of various point-location algorithms implemented in Cgal, including a newly devised Landmarks algorithm. Among the other algorithms studied are: a naïve...
Exact and efficient construction of Minkowski sums of convex polyhedra with applications (2006)
We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R 3. Our implementation is complete in the sense that it does not assume general...
Dynamic maintenance of molecular surfaces under conformational changes (2005)
We present an efficient algorithm for maintaining the boundary and surface area of protein molecules as they undergo conformational changes. We also describe a robust implementation of the algorithm...
The Visibility-Voronoi complex and its applications (2005)
Ron Wein, Jur P. Berg, Dan Halperin
We introduce a new type of diagram called the VV (c)-diagram (the Visibility–Voronoi diagram for clearance c), which is a hybrid between the visibility graph and the Voronoi diagram of polygons in...
Ron Wein, Dan Halperin, R. Wein, O. Ilushin, G. Elber, D. Halperin
We introduce a new approach to the problem of collision detection between a rotating milling-cutter of an NC-machine and a model of a solid workpiece, as the rotating cutter continuously moves near...
Advanced programming techniques applied to Cgal’s arrangement package (2005)
Ron Wein, Efi Fogel, Baruch Zukerman, Dan Halperin
Arrangements of planar curves are fundamental structures in computational geometry. Recently, the arrangement package of Cgal, the Computational Geometry Algorithms Library, has been redesigned and...
Advanced programming techniques applied to Cgal’s arrangement package (2005)
Ron Wein, Efi Fogel, Baruch Zukerman, Dan Halperin
Arrangements of planar curves are fundamental structures in computational geometry. Recently, the arrangement package of Cgal, the Computational Geometry Algorithms Library, has been redesigned and...
The Visibility-Voronoi complex and its applications (2005)
We introduce a new type of diagram called the VV (c)-diagram (the Visibility–Voronoi diagram for clearance c), which is a hybrid between the visibility graph and the Voronoi diagram of polygons in...
Advanced programming techniques applied to Cgal’s arrangement package (2005)
Ron Wein, Efi Fogel, Baruch Zukerman, Dan Halperin
Arrangements of planar curves are fundamental structures in computational geometry. Recently, the arrangement package of Cgal, the Computational Geometry Algorithms Library, has been redesigned and...
The Visibility-Voronoi complex and its applications (2005)
Ron Wein, Jur P. Berg, Dan Halperin
Abstract We introduce a new type of diagram called the VV(c)-diagram (the Visibility-Voronoi dia-gram for clearance c), which is a hybrid between the visibility graph and the Voronoi diagramof...
Video: Exact Minkowski sums of convex polyhedra (2005)
We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R 3. Our implementation is complete in the sense that it does not assume general...
Video: Exact Minkowski sums of convex polyhedra (2005)
We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R 3. Our implementation is complete in the sense that it does not assume general...
An empirical comparison of software for constructing arrangements of curved arcs (2004)
Berberich, Eric, Eigenwillig, Arno, Emiris, Ioannis, Fogel, Efraim, Hemmer, Michael, Halperin, Dan, ...
Deploying and Optimizing Squid in a Filesharing Application – p.4/16 (2004)
Dan Halperin, Dr. Manish Parashar, Cristina Schmidt, Pp Background, Napster Pp Model, Napserver Napserver, ...
computers, cell phones, palms, etc) on a network connect directly to each other instead of through a centralized server. Why? Scalability, speed, fault tolerance, etc. Deploying and Optimizing Squid...
Code flexibility and program efficiency by genericity: Improving cgal’s arrangements (2004)
Efi Fogel, Ron Wein, Dan Halperin
Abstract. Arrangements of planar curves are fundamental structures in computational geometry. We describe the recent developments in the arrangement package of Cgal, the Computational Geometry...
Dan Halperin, Dr. Manish Parashar, Cristina Schmidt, Hilbert Sfc, Squid Pp Model
• A hash table is ”a data structure that divides all elements into buckets to allow quick access to the elements. ” Hash function maps keys to buckets. • Index in Distributed Hash Table...
Itay Lotan, Fabian Schwarzer, Dan Halperin, Jean-claude Latombe
Monte Carlo simulation (MCS) is a common methodology to compute pathways and thermodynamic properties of proteins. A simulation run is a series of random steps in conformation space, each perturbing...
Code flexibility and program efficiency by genericity: Improving cgal’s arrangements (2004)
Efi Fogel, Ron Wein, Dan Halperin
Abstract. Arrangements of planar curves are fundamental structures in computational geometry. We describe the recent developments in the arrangement package of Cgal, the Computational Geometry...
Algorithm and Data Structures for Ecient Energy Maintenance during (2004)
Monte Carlo Simulation, Itay Lotan, Fabian Schwarzer, Dan Halperin, Jean-claude Latombe
Monte Carlo simulation (MCS) is a common methodology to compute pathways and thermodynamic properties of proteins. A simulation run is a series of random steps in conformation space, each perturbing...
Precise global collision detection in multi-axis NCmachining (2004)
Oleg Ilushin, Gershon Elber, Dan Halperin, Ron Wein
We introduce a new approach to the problem of collision detection in multi-axis NC-machining. Due to the directional nature (tool axis) of multi-axis NC-machining, space subdivision techniques are...
Continuous path verification in multi-axis NC-machining (2004)
Ron Wein, Gershon Elber, Oleg Ilushin, Dan Halperin
We introduce a new approach to the problem of collision detection between a rotating milling-cutter of an NC-machine and a model of a solid workpiece, as the rotating cutter continuously moves near...
Assigning transmembrane segments to helices in intermediate-resolution structures (2004)
Enosh, Angela, Fleishman, Sarel J., Ben-Tal, Nir, Halperin, Dan
Motivation: Transmembrane (TM) proteins that form α-helix bundles constitute approximately 50% of contemporary drug targets. Yet, it is difficult to determine their high-resolution (< 4 Å)...
Controlled Perturbation for Arrangements of Circles (2003)
Dan Halperin, Dan Halperin, Eran Leiserowitz, Eran Leiserowitz
of circles in the plane, we wish to construct the arrangement A(C) (namely the subdivision of the plane into vertices, edges and faces induced by C) using floating point arithmetic. We present an...
Improved implementation of controlled perturbation for arrangements of spheres (2003)
Eran Eyal, Eran Eyal, Dan Halperin, Dan Halperin
We describe modifications to the implementation of the perturbation scheme for arrangements of spheres presented by Halperin and Shelton [6], which they applied to computing molecular surfaces. The...
Controlled Perturbation for Arrangements of Circles (2003)
Dan Halperin, Eran Leiserowitz
of circles in the plane, we wish to construct the arrangement A(C) (namely the subdivision of the plane into vertices, edges and faces induced by C) using floating point arithmetic. We present an...
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...
Speeding up the incremental construction of the union of geometric objects in practice (2002)
Eti Ezra, Dan Halperin, Micha Sharir
We present a new incremental algorithm for constructing the union of n triangles in the plane. In our experiments, the new algorithm, which we call the Disjoint-Cover (DC) algorithm, performs...
Snap rounding is a well known method for converting arbitrary-precision arrangements of segments into a xed-precision representation. We point out that in a snap-rounded arrangement, the distance...
The 2-center problem with obstacles (2002)
Dan Halperin, Micha Sharir, Ken Goldberg
Given a set S of n points in the plane and a set O of pairwise disjoint simple polygons with a total of m edges, we wish to nd two congruent disks of smallest radius whose union covers S and whose...
Improved Construction of Vertical Decompositions of Three-Dimensional Arrangements (2002)
We present new results concerning the refinement of three-dimensional arrangements by vertical decompositions. First, we describe a new output-sensitive algorithm for computing the vertical...
Speeding Up the Incremental Construction of the Union of Geometric Objects in Practice (2002)
Eti Ezra, Dan Halperin, Micha Sharir
We present a new incremental algorithm for constructing the union of n triangles in the plane. In our experiments, the new algorithm, which we call the Disjoint-Cover (DC) algorithm, performs signi...
Controlled Perturbation for Arrangements of Polyhedral Surfaces (2002)
We describe a perturbation scheme to overcome degeneracies and precision problems for algorithms that manipulate polyhedral surfaces using fixed precision arithmetic. The perturbation algorithm is...
Hybrid Motion Planning: Coordinating Two Discs Moving Among Polygonal Obstacles in the Plane (2002)
The basic motion-planning problem is to plan a collision-free motion for an object moving among obstacles between free initial and goal positions, or to determine that no such motion exists. The...
Snap rounding revisited (2001)
Snap rounding is a well known method for converting arbitrary-precision arrangements of segments into a xed-precision representation. We point out that in a snap-rounded arrangement, the distance...
The design and implementation of planar maps in CGAL (2000)
Eyal Flato, Dan Halperin, Iddo Hanniel, Oren Nechushtan, Eti Ezra
Planar maps are fundamental structures in computational geometry. They are used to represent the subdivision of the plane into regions and have numerous applications. We describe the planar map...
Robust and efficient construction of planar Minkowski sums (2000)
The Minkowski sum (also known as the vector sum) of two sets P and Q in IR 2 is the set fp + q j p 2 P; q 2 Qg. Minkowski sums are useful in robot motion planning, computer-aided design and...
Two-dimensional arrangements in cgal and adaptive point location for parametric curves (2000)
Abstract. Given a collection C of curves in the plane, the arrangement of C is the subdivision of the plane into vertices, edges and faces induced by the curves in C. Constructing arrangements of...
The design and implementation of planar maps in CGAL (2000)
Eyal Flato, Dan Halperin, Iddo Hanniel, Oren Nechushtan, Eti Ezra
Planar maps are fundamental structures in computational geometry. They are used to represent the subdivision of the plane into regions and have numerous applications. We describe the planar map...
Robust Geometric Computing in Motion (2000)
In this paper we discuss the gap between the theory and practice of geometric algorithms. We then describe effors to settle this gap and facilitate the successful implementation of geometric...
An Empirical Comparison of Software for Constructing Arrangements of Curved Arcs (2000)
Sylvain Pion, Monique Teillaud, Efraim Fogel, Dan Halperin, Ron Wein, Ioannis Emiris, ...
Arrangements of planar curves are fundamental structures in computational geometry.
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
Robots are versatile mechanical devices equipped with actuators and sensors under the control
On-line Zone Construction in Arrangements of Lines in the Plane (1999)
Yuval Aharoni Dan, Dan Halperin, Iddo Hanniel, Sariel Har-peled, Chaim Linhart
. Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that...
On-line zone construction in arrangements of lines in the plane (1999)
Chaim Linhart, Dan Halperin, Sariel Har-Peled, Iddo Hanniel
Given a finite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that...
The Design and Implementation of Planar Maps in CGAL (1999)
Eyal Flato, Dan Halperin, Iddo Hanniel, Oren Nechushtan
Planar maps are fundamental structures in computational geometry. They are used to represent the subdivision of the plane into regions and have numerous applications. We describe the planar map...
On-line Zone Construction in Arrangements of Lines in the Plane (1999)
Yuval Aharoni, Dan Halperin, Iddo Hanniel, Sariel Har-peled, Chaim Linhart
. Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that...
Daniel Cohen-or, Gadi Fibich, Dan Halperin, Eyal Zadicario
Computing the visibility of out-door scenes is often much harder than of in-door scenes. A typical urban scene, for example, is densely occluded, and it is effective to precompute its visibility...
Shape Tolerance in Feeding and Fixturing (1998)
Jingliang Chen, Ken Goldberg, Mark H. Overmars, Dan Halperin
Parts are not ideal. Designers and machinists cope with variation in part shape by specifying tolerance zones around a nominal part geometry: all parts that #t within the zone form a tolerance class....
On the Area Bisectors of a Polygon (1998)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon #possibly with holes# in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce di#erent...
Dan Halperin, Lydia Kavraki, Jean-Claude Latombe
Introduction Robots are versatile mechanical devices equipped with actuators and sensors under the control of a computing system. They perform tasks by executing motions in the physical space. This...
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...
Daniel Cohen-or, Gadi Fibich, Dan Halperin, Eyal Zadicario
Computing the visibility of out-door scenes is often much harder than of in-door scenes. A typical urban scene, for example, is densely occluded, and it is effective to precompute its visibility...
A General Framework for Assembly Planning: The Motion Space Approach (1998)
Dan Halperin, Jean-claude Latombe, Randall H. Wilson
Assembly planning is the problem of finding a sequence of motions to assemble a product from its parts. We present a general framework for finding assembly motions based on the concept of motion...
On the Number of Regular Vertices of the Union of Jordan Regions (1998)
Boris Aronov, Alon Efrat, Dan Halperin, Micha Sharir
Let C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. Let U denote the union of C....
Shape Tolerance in Feeding and Fixturing (1998)
Jingliang Chen, Ken Goldberg, Mark Overmars, Dan Halperin, Karl Bohringer, Yan Zhuang
Parts are not ideal. Designers and machinists cope with variation in part shape by specifying tolerance zones around a nominal part geometry: all parts that fit within the zone form a tolerance...
A General Framework for Assembly Planning: The Motion Space Approach (1998)
Dan Halperin, Jean-claude Latombe, Randall H. Wilson
Assembly planning is the problem of finding a sequence of motions to assemble a product from its parts. We present a general framework for finding assembly motions based on the concept of motion...
Introduction Robots are versatile mechanical devices equipped with actuators and sensors under the control of a computing system. They perform tasks by executing motions in the physical space. This...
On the Area Bisectors of a Polygon (1998)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different...
A General Framework for Assembly Planning: The Motion Space Approach (1998)
Dan Halperin, Jean-claude Latombe, Randall H. Wilson
Assembly planning is the problem of finding a sequence of motions to assemble a product from its parts. We present a general framework for finding assembly motions based on the concept of motion...
The Dynamic Servers Problem (1998)
Moses Charikar, Dan Halperin, Rajeev Motwani
Introduction. We introduce the dynamic servers problem, a generalization of the k-server problem [11]. This problem is a simultaneous abstraction for problems arising in a variety of applications...
The Dynamic Servers Problem (1998)
Moses Charikar, Dan Halperin, Rajeev Motwani
We present a generalization of the k-server problem, called dynamic servers, where the number of servers is not fixed a priori; rather, the algorithm is free to increase and decrease the number of...
Eurographics N. Ferreira, Daniel Cohen-or, Gadi Fibich, Dan Halperin, Eyal Zadicario
Computing the visibility of out-door scenes is often much harder than of in-door scenes. A typical urban scene, for example, is densely occluded, and it is effective to precompute its visibility...
The Dynamic Servers Problem (1998)
Moses Charikar, Dan Halperin, Rajeev Motwani
We present a generalization of the k-server problem, called dynamic servers, where the number of servers is not fixed a priori; rather, the algorithm is free to increase and decrease the number of...
A Perturbation Scheme for Spherical Arrangements with Application to Molecular Modeling (1997)
Halperin, Dan, Shelton, Christian R.
We describe a software package for computing and manipulating the subdivision of a sphere by a collection of (not necessarily great) circles and for computing the boundary surface of the union of...
A Perturbation Scheme for Spherical Arrangements with Application to Molecular Modeling (1997)
Halperin, Dan, Shelton, Christian R.
We describe a software package for computing and manipulating the subdivision of a sphere by a collection of (not necessarily great) circles and for computing the boundary surface of the union of...
Dan Halperin, E. Kavraki, Jean-Claude Latornbe
Robotics is concerned with the generation of computer-controlled motions of physical objects in a wide variety of settings. Because physical objects define spatial distributions in 3-space, geometric...
Dan Halperin, Lydia Kavraki, Jean-claude Latombe
Robotics is concerned with the generation of computer-controlled motions of physical objects in a wide variety of settings. Because physical objects define spatial distributions in 3-space, geometric...
On the Area Bisectors of a Polygon (1997)
Bruce Randall Donald, Dan Halperin
We consider the family of lines that arearea bisectors of a polygon #possibly with holes# in the plane. We say that two bisectors of a polygon P arecombinatorially distinct if they induce di#erent...
The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields (1997)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of area bisectors of a polygon #possibly with holes# in the plane. Wesay that two bisectors of a polygon P are combinatorially distinct if they induce di#erent partitionings of...
A Perturbation Scheme for Spherical Arrangements with Application to Molecular Modeling (1997)
Dan Halperin, Christian R. Shelton
: We describe a software package for computing and manipulating the subdivision of a sphere by a collection of (not necessarily great) circles and for computing the boundary surface of the union of...
On the Area Bisectors of a Polygon (1997)
Karl-Friedrich Bohringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different...
A Perturbation Scheme for Spherical Arrangements with Application to Molecular Modeling (1997)
Dan Halperin, Christian R. Shelton
We describe a software package for computing and manipulating the subdivision of a sphere by a collection of (not necessarily great) circles and for computing the boundary surface of the union 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...
INTRODUCTION Given a finite collection S of geometric objects such as hyperplanes or spheres in R d , the arrangement A(S) is the decomposition of R d into connected open cells of dimensions 0; 1; :...
Efficient motion planning for an L-shaped object (1997)
Dan Halperin, Mark H. Overmars, Micha Sharir
We present an algorithm that solves the following motion-planning problem. Given an L-shaped body L and a 2-dimensional region with n point obstacles, decide whether there is a continuous motion...
The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields (1997)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different partitionings...
The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields (1997)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different partitionings...
On the Area Bisectors of a Polygon (1997)
Karl-Friedrich Bohringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different...
The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields (1997)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of area bisectors of a polygon in the plane. We show that there are polygons with n vertices that have \Omega\Gamma n 2 ) combinatorially distinct area bisectors, and we...
On the Area Bisectors of a Polygon (1997)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different...
On the Area Bisectors of a Polygon (1997)
Karl-Friedrich Bohringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different...
On the Area Bisectors of a Polygon (1997)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different...
On the Area Bisectors of a Polygon (1997)
Karl-Friedrich Böhringer, Bruce Randall Donald, Dan Halperin
We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different...
Geometric manipulation of flexible ligands (1996)
Paul W. Finn, Dan Halperin, Lydia E. Kavraki, Rajeev Motwahl A
Abstract. In recent years an effort has been made to supplement traditional methods for drug discovery by computer-assisted "structure-based design. " The structure-based approach...
Assembly Partitioning along Simple Paths: the Case of Multiple Translations (1996)
Dan Halperin, Randall H. Wilson
We consider the following problem that arises in mechanical assembly planning: given an assembly, identify a subassembly that can be removed as a rigid object without disturbing the rest of the...
Geometric Manipulation of Flexible Ligands (1996)
Paul W. Finn, Dan Halperin, Lydia E. Kavraki, Rajeev Motwani, Christian Shelton, Suresh Venkatasubramanian
. In recent years an effort has been made to supplement traditional methods for drug discovery by computer-assisted "structure-based design." The structure-based approach involves (among...
Dynamic Maintenance of Kinematic Structures (1996)
Dan Halperin, Jean-Claude Latombe, Rajeev Motwani
Data Structure In this section we give a formal description of our data structuring problem, henceforth referred to as the kinematic data structure problem. We are required to maintain a data...
Geometric manipulation of flexible ligands (1996)
Dan Halperin, Lydia Kavraki, Jean-claude Latombe, Rajeev Motwani, Christian Shelton, Suresh Venkatasubramanian
In recent years an effort has been made to supplement traditional methods for drug discovery by computerassisted “structure-based design. ” The structure-based approach involves (among other...
Leonidas J. Guibas, Dan Halperin, Hirohisa Hirukawa, Jean-claude Latombe
We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an in nitesimal translation...
The Complexity of a Single Face of a Minkowski Sum (1995)
Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink
This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...
Arrangements and their Applications in Robotics: Recent Developments (1995)
this paper addresses and survey previous work on these problems. We state the basic new results in Section 3. We exemplify the usefulness of these results by applying them to problems involving robot...
Assembly Partitioning along Simple Paths: the Case of Multiple Translations (1995)
Dan Halperin, Randall H. Wilson
We consider the following problem that arises in assembly planning: given an assembly, identify a subassembly that can be removed as a rigid object without disturbing the rest of the assembly. This...
Vertical Decompositions for Triangles in 3-Space (1995)
Mark De Berg, Leonidas J. Guibas, Dan Halperin
We prove that, for any constant " ? 0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n 2+" + K), where K is the complexity of the...
Vertical Decomposition of Arrangements of Hyperplanes in Four Dimensions (1995)
Leonidas J. Guibas, Dan Halperin, Jirí Matousek, Micha Sharir
We show that, for any collection H of n hyperplanes in ! 4 , the combinatorial complexity of the vertical decomposition of the arrangement A(H) of H is O(n 4 log n). The proof relies on properties of...
Almost tight upper bounds for the single cell and zone problems in three dimensions (1995)
We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of n low-degree algebraic surface patches in 3-space. We show that this complexity is O(n
Leonidas J. Guibas, Dan Halperin, H. Hirukawa, J.C. Latombe, R.H. Wilson, Hirohisa Hirukawa, ...
We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an infinitesimal...
A Near-Quadratic Algorithm for Planning the Motion of a Polygon in a Polygonal Environment (1995)
We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We present an algorithm that...
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
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
Spheres, molecules, and hidden surface removal (1994)
Dan Halperin, Dan Halperin, Dan Halperin, Mark H. Overmars, Mark H. Overmars, Mark H. Overmars
z We devise techniques to manipulate a collection of loosely interpenetrating spheres in three-dimensional space. Our study is motivated by the representation and manipulation of molecular...
We consider the problem of bounding the complexity of the lower envelope of n surface patches in 3-space, all algebraic of constant maximum degree, and bounded by algebraic arcs of constant maximum...
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...
Vertical Decompositions for Triangles in 3-Space (1994)
Mark De Berg, Leonidas J. Guibas, Dan Halperin
We prove that, for any constant " ? 0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n 2+" + K), where K is the complexity of the...
Arrangements of Segments that Share Endpoints: Single Face Results (1994)
Esther M. Arkin, Dan Halperin, Klara Kedem, Nir Naor
We provide new combinatorial bounds on the complexity of a face in an arrangement of segments in the plane. In particular, we show that the complexity of a single face in an arrangement of n line...
Spheres, Molecules, and Hidden Surface Removal (1994)
Dan Halperin, Mark H. Overmars
We devise techniques to manipulate a collection of loosely interpenetrating spheres in threedimensional space. Our study is motivated by the representation and manipulation of molecular...
Robot Motion Planning and the Single Cell Problem in Arrangements (1994)
Robot motion planning has become a central topic in robotics and has been studied using a variety of techniques. One approach, followed mainly in computational geometry, aims to develop...
We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements of n surfaces in 3-space where the lower bound for this quantity is \Omega\Gamma...
Efficient Algorithms for Exact Motion Planning amidst Fat Obstacles (1993)
Dan Halperin, Mark H. Overmars
The complexity of exact motion planning algorithms highly depends on the complexity of the robot's free space, i.e., the set of all collision-free placements of the robot. Theoretically, the...
The Complexity of the Free Space for a Robot Moving Amidst Fat Obstacles (1993)
Dan Halperin, Mark H. Overmars
We propose a new definition of fatness of a geometric object and compare it with alternative definitions. We show that, under some realistic assumptions, the complexity of the free space for a robot...
Combinatorial Complexity of Translating a Box in Polyhedral 3-Space (1993)
We study the space of free translations of a box amidst polyhedral obstacles with n vertices. We show that the combinatorial complexity of this space is O(n 2 ff(n)) where ff(n) is the inverse...
Arrangements of Segments that Share Endpoints: Single Face Results (1991)
Esther M. Arkin, Dan Halperin, Klara Kedem
(1) z
On Disjoint Concave Chains in Arrangements of (Pseudo) Lines - Corrigendum (1991)
In the paper mentioned in the title [1] we have asserted that the maximum number of edges of m pairwise-disjoint x-monotone concave polygonal chains, contained in the union of n lines or pseudo...
Sparse Arrangements and the Number of Views of Polyhedral Scenes (1991)
Mark De Berg, Dan Halperin, Mark H. Overmars, Marc Van Kreveld
In this paper we study several instances of the problem of determining the maximum number of topologically distinct two-dimensional images that three-dimensional scenes can induce. To bound this...
MolAxis: a server for identification of channels in macromolecules
Yaffe, Eitan, Fishelovitch, Dan, Wolfson, Haim J., Halperin, Dan, Nussinov, Ruth
MolAxis is a freely available, easy-to-use web server for identification of channels that connect buried cavities to the outside of macromolecules and for transmembrane (TM) channels in proteins....
Rapid Sampling of Molecular Motions with Prior Information Constraints
Raveh, Barak, Enosh, Angela, Schueler-Furman, Ora, Halperin, Dan
Proteins are active, flexible machines that perform a range of different functions. Innovative experimental approaches may now provide limited partial information about conformational changes along...
Generation, Comparison, and Merging of Pathways between Protein Conformations: Gating in K-Channels
Enosh, Angela, Raveh, Barak, Furman-Schueler, Ora, Halperin, Dan, Ben-Tal, Nir
We present a general framework for the generation, alignment, comparison, and hybridization of motion pathways between two known protein conformations. The framework, which is rooted in probabilistic...