Personal tools
You are here: Home Dan Halperin Publications Dan Halperin's Publications
« October 2014 »
October
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
262728293031
Log in


Forgot your password?
 

Dan Halperin's Publications

Publications are listed in reverse chronological order of their latest version, according to the following categories:

  • Robust Geometric Computing and CGAL
  • Arrangements
  • Robotics
  • Molecular Modeling
  • Miscellaneous
  • Surveys
  • Books and Proceedings
  •  

    Robust Geometric Computing and CGAL

    • Michael Hemmer, Ophir Setter, Dan Halperin
      Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space - with Fast Point-Location
      ESA (1),pages 398-409, 2010.
      [link][bibtex] [project page]
    • Dan Halperin
      Controlled Perturbation for Certified Geometric Computing with Fixed-Precision Arithmetic
      ICMS, pages 92-95, 2010.
      [link][bibtex]
    • Naama Mayer, Efi Fogel, Dan Halperin
      Fast and robust retrieval of Minkowski sums of rotating convex polyhedra in 3-space
      Symposium on Solid and Physical Modeling, pages 1-10, 2010.
      [link][bibtex] [project page]
    • Eitan Yaffe, Dan Halperin
      Approximating the Pathway Axis and the Persistence Diagrams for a Collection of Balls in 3-Space
      Discrete & Computational Geometry 44(3), pages 660-685, 2010.
      [link][bibtex] [project page]
    • Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein
      Arrangements on Parametric Surfaces I: General Framework and Infrastructure
      Mathematics in Computer Science 4(1), pages 45-66, 2010.
      [link][bibtex][project page]
    • Eric Berberich, Efi Fogel, Dan Halperin, Michael Kerber, Ophir Setter
      Arrangements on Parametric Surfaces II: Concretizations and Applications
      Mathematics in Computer Science 4(1), pages 67-91, 2010.
      [link][bibtex][project page]
    • Ophir Setter, Micha Sharir, Dan Halperin
      Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space
      Transactions on Computational Science 9, pages 1-27, 2010.
      [link][bibtex] [project page]
    • Ophir Setter, Micha Sharir, and Dan Halperin
      Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space,
      In Proceedings of the 6th annual International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), pages 43-52, Copenhagen, Denmark, June 2009. [bibtex] [project page]
    • Ophir Setter and Dan Halperin
      Exact construction of minimum-width annulus of disks in the plane
      In Abstracts of 25th European Workshop on Computational Geometry, pages 317-320, 2009
      [pdf] [bibtex] [project page]
    • E. Fogel, O. Setter and D. Halperin
      Exact implementation of arrangements of geodesic arcs on the sphere with applications
      In Abstracts of 24th European Workshop on Computational Geometry, pp 83-86, 2008
      [pdf] [bibtex] [project page]
    • E. Fogel, O. Setter and D. Halperin
      Arrangements of geodesic arcs on the sphere
      In Proceedings of the 24th ACM Annual Symposium on Computational Geometry, pages 218-219, 2008
      [movie - additional information][pdf] [bibtex] [project page]
    • I. Haran and D. Halperin
      An experimental study of point location in planar arrangements in CGAL
       ACM Journal of Experimental Algorithmics, 13, 2008
      [pdf] [bibtex] [project page]
      A preliminary version appeared in ALENEX 2006, Miami, Florida, 2006
    • E. Fogel, D. Halperin, L. Kettner, M. Teillaud, R. Wein and N. Wolpert
      Arrangements
      Effective Computational Geometry for Curves and Surfaces, Jean-Daniel Boissonnat and Monique Teillaud (eds.), Springer, Mathematics and Visualization series, 2007, Chapter 1, pp. 1-66. 
      [link] [bibtex
    • E. Berberich, E. Fogel, D. Halperin, K. Mellhorn, and R. Wein
      Sweeping and maintaning two-dimensional arrangements on surfaces: a first step
      Proceedings 15th Annual European Symposium on Algorithms (ESA) 2007, pp. 645-656
      [pdf] [bibtex] [project page]
    • M. de Berg, D. Halperin and M. Overmars
      An intersection-sensitive algorithm for snap rounding
      Computational Geometry: Theory and Applications 36, 2007, pp. 159-165.
      [pdf] [bibtex]
    • E. Fogel and D. Halperin
      Exact and efficient construction of Minkowski sums of convex polyhedra with applications
      Computer Aided Design, 39(11):929-940, 2007. [bibtex] [project page]
      A prelimenary version appeared in Proc. 8th Workshop on Algorithm Engineering and Experiments (ALENEX) 2006
      [pdf] [bibtex]
    • R. Wein, E. Fogel, B. Zukerman and D. Halperin
      Advanced programming techniques applied to CGAL's arrangement package
      Proc. Library-Centric Software Design Workshop, LCSD'05, San Diego, California, 2005
      [pdf] [bibtex]
    • E. Fogel and D. Halperin
      Video: Exact Minkowski sums of convex polyhedra
      Proc. 21st ACM Symposium on Computational Geometry, SoCG 2005, Pisa, Italy, 2005, 382-383.
      [movie] [pdf] [bibtex] [project page]
    • E. Fogel, R. Wein and D. Halperin
      Code flexibility and program efficiency by genericity: Improving CGAL's arrangements
      Proc. 12th Annual European Symposium on Algorithms (ESA), Bergen, Norway, 2004, 664-676.
      [pdf] [bibtex]
    • D. Halperin and E. Leiserowitz
      Controlled perturbation for arrangements of circles
      International Journal of Computational Geometry and Applications, 14 (4 & 5), 2004, pp. 277-310. Special issue, papers from SoCG 2003.
      [pdf] [bibtex] [project page]
      A preliminary version appeared in Proc. 19th ACM Symposium on Computational Geometry, SoCG 2003, San Diego, 264-273
    • C. Linhart, D. Halperin, S. Har-Peled and I. Hanniel
      On-line zone construction in arrangements of lines in the plane
      International Journal of Computational Geometry and Applications, 13:6 (2003), pp. 463-485.
      [pdf] [bibtex] [project page]
      A preliminary version with Y. Aharoni appeared in Proc. 3rd International Workshop on Algorithm Engineering (WAE), London, 1999,Springer LNCS Vol. 1668, 139-153
    • D. Halperin and E. Packer
      Iterated snap rounding
      Computational Geometry: Theory and Applications, 23(2), 2002, pp. 209-222.
      [pdf] [bibtex] [project page]
      A preliminary version appeared in Abstracts 17th European Workshop on Computational Geometry, Berlin, 2001, 82-85
    • D. Halperin
      Robust geometric computing in motion
      International Journal of Robotics Research, 21 (3), 2002, pp. 219-232. Appeared in: Algorithmic and Computational Robotics: New Dimensions (WAFR '00). B.R. Donald and K.M. Lynch and D. Rus (eds.,) A.K. Peters, Wellesley, 2001, pp. 9-22. Invited talk at WAFR 2000, Workshop on Algorithmic Foundations of Robotics , Dartmouth College, March 2000.
      [pdf] [bibtex]
    • E. Ezra, D. Halperin and M. Sharir
      Speeding up the incremental construction of the union of geometric objects in practice
      Computational Geometry: Theory and Applications, 27 (2004), pp. 63-85. Special issue, papers from the 18th European Workshop on Computational Geometry, Warsaw, April 2002.
      [pdf] [bibtex] [project page]
      A preliminary version appeared in Proc. 10th Europen Symposium on Algorithms (ESA), Rome, 2002, 473-484.
      See also article entitled "Efficient Construction of the Union of Geometric Objects" in Proc. 18th European Workshop on Computational Geometry, Warsaw, 2002, pp.56-60
    • E. Flato, E. Fogel, D. Halperin and E. Leiserowitz
      Video: Exact Minkowski sums and applications
      Proc. 18th ACM Symposium on Computational Geometry, Barcelona, 2002, 273-274.
      [movie] [bibtex] [project page]
    • P.K. Agarwal, E. Flato and D. Halperin
      Polygon decomposition for efficient construction of Minkowski sums
      Computational Geometry: Theory and Applications, Special Issue, selected papers from the European Workshop on Computational Geometry, Eilat, 2000, vol. 21 (2002), 39-61.
      [pdf] [bibtex
      preliminary version appeared in Proc. 8th European Symposium on Algorithms (ESA), Saarbrücken, 2000. Springer LNCS Vol. 1879, 20-31.
      See also Eyal Flato's thesis [pdf] [bibtex] [project page]
    • E. Flato and D. Halperin
      Robust and efficient construction of planar Minkowski sums
      Abstracts 16th European Workshop on Computational Geometry, Eilat, 2000, 85-88.
      [pdf] [bibtex] [project page]
      See also Eyal Flato's thesis [pdf] [bibtex] [project page]
    • I. Hanniel and D. Halperin
      Two-dimensional arrangements in CGAL and adaptive point location for parametric curves
      Proc. 4th International Workshop on Algorithm Engineering (WAE), Saarbrücken, LNCS Vol. 1982, Springer, 2000, 171-182.
      [pdf] [bibtex] [project page]
      See also Iddo Hanniel's thesis [pdf] [bibtex]
    • E. Flato, D. Halperin, I. Hanniel, O. Nechushtan and E. Ezra
      The design and implementation of planar maps in CGAL
      The ACM Journal of Experimental Algorithmics Volume 5, 2000, pp. 1-23.
      [pdf] [bibtex] [ project page]
      A preliminary version appeared in Proc. 3rd International Workshop on Algorithm Engineering (WAE), London, 1999, Springer LNCS Vol. 1668, 154-168
    • D. Halperin and C.R. Shelton
      A perturbation scheme for spherical arrangements with application to molecular modeling (the full version, MIT AI MEMO)
      Computational Geometry: Theory and Applications 10 (4), 1998, pp. 273-288.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 13th ACM Symposium on Computational Geometry, Nice, 1997, 183-192. 
    • D. Halperin and S. Raab
      Controlled perturbation for arrangements of polyhedral surfaces.
      [pdf]
      A preliminary version entitled: Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes by S. Raab appeared in Proc. 15th ACM Symposium on Computational Geometry, Miami, 1999, 163-172. [bibtex] [project page]
      See also Sigal Raab's thesis [pdf] [bibtex]

     

    Arrangements

  • Papers reporting on the experimental study of arrangements including arrangements in CGAL appear above under Robust Geometric Computing and CGAL
  •  

    • N. Alon, O. Nechushtan, D. Halperin, and M. Sharir
      The complexity of the outer face in arrangements of random segments
      Proc. of the Twenty-fourth Annual Symposium on Computational Geometry SOCG, 2008, pp 69-78.
      [link] [bibtex] [project page]
    • D. Halperin
      Arrangements
      CRC Handbook of Discrete and Computational Geometry, 2nd Edition, J.E. Goodman and J. O'Rourke (eds.), CRC Press, Inc., Boca Raton, FL, 2004, pp. 529-562.
      [link] [bibtex
    • H. Shaul and D. Halperin
      Improved construction of vertical decompositions of 3D arrangements
      Proc. 18th ACM Symposium on Computational Geometry, Barcelona, 2002, 283-292.
      [pdf] [bibtex] [project page]
      Also appeared in Proc. 18th European Workshop on Computational Geometry, Warsaw, 2002, pp. 101-105
    • B. Aronov, A. Efrat, D. Halperin, and M. Sharir
      On the number of regular vertices of the union of Jordan regions
      Discrete and Computational Geometry, 25 (2001), 203-220.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 6th Scandinavian Workshop on Algorithm Theory (SWAT), Stockholm, 1998, pp. 322-334.
    • M. de Berg, D. Halperin, M.H. Overmars and M. van Kreveld
      Sparse arrangements and the number of views of polyhedral scenes
      International Journal of Computational Geometry and Applications 7 (1997), 175-195.
      [pdf] [bibtex]
    • M. de Berg, L.J. Guibas and D. Halperin
      Vertical decompositions for triangles in 3-space
      Discrete and Computational Geometry, 15 (1996), 36--61.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 10th ACM Symposium on Computational Geometry, Stony Brook, 1994, 1-10.
    • D. Halperin and M. Sharir
      Almost tight upper bounds for the single cell and zone problems in three dimensions
      Discrete and Computational Geometry, special issue of papers from the 10th ACM Symposium on Computational Geometry, 14 (1995), 385--410.
      [pdf] [bibtex
      A preliminary version appeared in Proc. 10th ACM Symposium on Computational Geometry, Stony Brook, 1994, 11-20.
    • L.J. Guibas, D. Halperin, J. Matousek and M. Sharir
      On vertical decomposition of arrangements of hyperplanes in four dimensions
      Discrete and Computational Geometry 14 (1995), 113--122.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 5th Canadian Conference on Computational Geometry, Waterloo, 1993, pp. 127-132.
    • S. Har-Peled, T. M. Chan, B. Aronov, D. Halperin and J. Snoeyink
      The complexity of a single face of a Minkowski sum
      Proc. 7th Canadian Conference on Computational Geometry, University Laval, Quebec, 1995, pp. 91-96 .
      [pdf] [bibtex]
    • D. Halperin and M. Sharir
      Arrangements and their applications in robotics: Recent developments
      The Algorithmic Foundations of Robotics, K. Goldberg, D. Halperin, J.C. Latombe and R. Wilson, Eds., A.K. Peters, Boston, MA, 1995, 495--511.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 1st Workshop on the Algorithmic Foundations of Robotics, San Francisco, 1994.
    • E.M. Arkin, D. Halperin, K. Kedem, J.S.B. Mitchell and N. Naor
      Arrangements of segments that share endpoints: Single face results
      Discrete and Computational Geometry 13 (1995), L\'aszl\'o Fejes T\'oth Festschrift, 257--270.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 7th ACM Symposium on Computational Geometry, North Conway, 1991, pp. 324-333.
    • D. Halperin and M. Sharir
      New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
      Discrete and Computational Geometry 12 (1994), 313-326.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 9th ACM Symposium on Computational Geometry, San Diego, 1993, 11-18.
    • D. Halperin
      On the complexity of a single cell in certain arrangements of surfaces related to motion planning
      Discrete and Computational Geometry 11 (1994), 1-33
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 7th ACM Symposium on Computational Geometry, North Conway, 1991, pp. 314-323.
    • D. Halperin and M. Sharir
      On disjoint concave chains in arrangements of (pseudo) lines
      Information Processing Letters 40 (1991), 189-192.
      Corrigendum
      ibid 51 (1994),53-56.
      [pdf] [bibtex]

     

    Robotics

    • Barak Raveh, Angela Enosh, Dan Halperin
      A Little More, a Lot Better: Improving Path Quality by a Simple Path Merging Algorithm
      CoRR, abs/1001.2391, 2010.
      [link] [bibtex][project page]
    • Itamar Berger, Bosmat Eldar, Gal Zohar, Barak Raveh, Dan Halperin
      Improving the Quality of Non-Holonomic Motion by Hybridizing C-PRM Paths
      CoRR, abs/1009.4787, 2010.
      [link] [bibtex]
    • Efi Fogel and Dan Halperin
      Polyhedral assembly partitioning with infinite translations or the importance of being exact
      Proc. of the 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2008, to appear
      [pdf] [bibtex] [project page]
    • R. Wein, J.P. van den Berg and D. Halperin
      Planning high-quality paths and corridors amidst obstacles
       Algorithmic Foundations of Robotics VII, pp 491-506, 2008
      [pdf] [bibtex] [project page]
    • R. Wein, J.P. van den Berg, and D. Halperin
      The visibility-Voronoi complex and its applications
      Computational Geometry: Theory and Applications, 36 (1) 2007, pp. 66-87.
      [pdf] [bibtex] [project page]
      A preliminary version appeared in Proc. 21st ACM Symposium on Computational Geometry, Pisa, June 2005, 63-72.
    • R. Wein, J.P. van den Berg, and D. Halperin
      Planning near-optimal corridors amidst obstacles (full version: Planning high-quality paths and corridors amidst obstacles)
      Proc. 7th International Workshop on the Algorithmic Foundations of Robotics, New York City, July 2006.
      [link] [bibtex] [project page]
    • O. Ilushin, G. Elber, D. Halperin and R. Wein and M.-S. Kim
      Precise global collision detection in multi-axis NC-machining
      Computer-Aided Design, 37(9), 2005, pp. 909-920.
      [pdf] [bibtex] [project page]
      A preliminary version appeared in Proc. International CAD Conference, Thailand, May 2004, pp. 233-243. 
    • R. Wein, O. Ilushin, G. Elber and D. Halperin
      Continuous path verification in multi-axis NC-machining
      International Journal of Computational Geometry and Applications, 15 (4) 2005, pp. 351-378.
      Special issue, dedicated to papers from the 20th ACM Symposium on Computational Geometry,Brooklyn, June, 2004.
      [pdf] [bibtex] [project page]
      A preliminary version appeared in Proc. 20th ACM Symposium on Computational Geometry, Brooklyn, June 2004, pp. 86-95.
    • D. Halperin, L. Kavraki, and J.-C. Latombe
      Robotics
      CRC Handbook of Discrete and Computational Geometry, 2nd Edition, J.E. Goodman and J. O'Rourke (eds.), CRC Press, Inc., Boca Raton, FL, 2004, pp. 1065-1093. 
      [link] [bibtex]
    • S. Hirsch and D. Halperin
      Hybrid motion planning: Coordinating two discs moving among polygonal obstacles in the plane
      Proc. 5th Workshop on Algorithmic Foundations of Robotics (WAFR), Nice, 2002, 225-241.
      [pdf] [bibtex] [project page]
    • D. Halperin, M. Sharir and K. Goldberg
      The 2-center problem with obstacles
      Journal of Algorithms 42 (2002), pp. 109-134.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 16th ACM Symposium on Computational Geometry, Hong Kong, 2000, 80-90.
    • J. Chen, K. Goldberg, M. Overmars, D. Halperin, K.F. Böhringer, and Y. Zhuang
      Computing tolerance parameters for fixturing and feeding
      The Assembly Automation Journal , 22 (2002), 163-172.
      [link] [bibtex]
      A preliminary version entitled: Shape Tolerance in Feeding and Fixturing, appeared in: The Algorithmic Foundations of Robotics, P.K. Agarwal, L. Kavraki, and M. Mason, Eds., A.K. Peters, Boston, MA, 1998, 297-311.
    • D. Halperin, J.-C. Latombe and R.H. Wilson
      A general framework for assembly planning: The motion space approach
      Algorithmica , 26 (2000), 577--601
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 14th ACM Symposium on Computational Geometry , Minneapolis, 1998, 9-18
    • K.F. Böhringer, B.R. Donald and D. Halperin
      On the area bisectors of a polygon
      Discrete and Computational Geometry, 22 (1999), 269-285.
      [pdf] [bibtex]
      A preliminary version entitled: The area bisectors of a polygon and force equilibria in programmable vector fields appeared in: Proc. 13th ACM Symposium on Computational Geometry, Nice, 1997, pp. 457-459.
    • D. Halperin, L. Kavraki, and J.-C. Latombe
      Robot algorithms
      CRC Algorithms and Theory of Computation Handbook M. Atallah (editor), CRC Press, Inc., Boca Raton, FL, 1999, Chapter 21
      [link] [bibtex]
    • L.J. Guibas, D. Halperin, H. Hirukawa, J.-C. Latombe and R.H. Wilson
      Polyhedral assembly partitioning using maximally covered cells in arrangements of convex polytopes
      Int. J. of Computational Geometry and its applications, 8(2), 1998, 179-199.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. IEEE International Conference on Robotics and Automation, Nagoya, Japan, 1995, 2553-2560.
    • D. Halperin and C.-K. Yap
      Combinatorial complexity of translating a box in polyhedral 3-space
      Computational Geometry: Theory and Applications, 9, 1998, 181-196.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 9th ACM Symposium on Computational Geometry, San Diego, 1993, pp. 29-37.
    • D. Halperin and R.H. Wilson
      Assembly partitioning along simple paths: The case of multiple translations 
      Advanced Robotics , 11 ,1997, 127-146.
      [pdf] [bibtex]
      A preliminary version appeared in IEEE International Conference on Robotics and Automation, Nagoya, Japan, 1995, 1585-1592.
    • D. Halperin and M. Sharir
      A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
      Discrete and Computational Geometry, 16 ,1996, 121-134.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 5th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, 1993, 382-391.
    • P. Agarwal, M. de Berg, D. Halperin and M. Sharir
      Efficient generation of k-directional assembly sequences
      Proc. 7th ACM-SIAM Symp. on Discrete Algorithms ,1996, 122-131.
      [pdf] [bibtex]
    • K.Y. Goldberg, D. Halperin, J.-C. Latombe and R.H. Wilson (editors)
      Algorithmic Foundations of Robotics A.K. Peters, Wellseley, MA, 1995.
      [link] [bibtex]
    • M. de Berg, L.J. Guibas, D. Halperin, M.H. Overmars, O. Schwarzkopf, M. Sharir and M. Teillaud
      Reaching a goal with directional uncertainty
      Theoretical Computer Science 140 ,1995, 301-317.
      [link] [bibtex]
      A preliminary version appeared in Proc. 4th International Symposium on Algorithms and Computation (ISAAC '93), Hong Kong, 1993, 1-10.
    • D. Halperin
      Robot motion planning and the single cell problem in arrangements
      Journal of Intelligent and Robotic Systems 11 ,1994, 45-65.
      [pdf] [bibtex]
    • A.F. van der Stappen, D. Halperin and M.H. Overmars
      The complexity of the free space for a robot moving amidst fat obstacles
      Computational Geometry: Theory and Applications 3 ,1993, 353-373.
      [pdf] [bibtex]
    • A.F. van der Stappen, D. Halperin and M.H. Overmars
      Efficient algorithms for exact motion planning amidst fat obstacles
      Proc. IEEE International Conference on Robotics and Automation, Atlanta, 1993, Vol. 1, pp.297-304.
      [pdf] [bibtex]
    • D. Halperin
      Algorithmic motion planning via arrangements of curves and of surfaces
      Ph.D Thesis, Computer Science Department, Tel Aviv University, Tel Aviv, July 1992.
      [bibtex]
    • D. Halperin, M.H. Overmars and M. Sharir
      Efficient motion planning for an L-shaped object
      SIAM Journal on Computing 21 (1992), 1-23
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 5th ACM Symposium on Computational Geometry, Saarbrücken, 1989, pp. 156-166.
    • D. Halperin and M. Sharir
      Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
      Computational Geometry: Theory and Applications 1 ,1992, 269-303.
      [link] [bibtex]
      A preliminary version appeared in Proc. 2nd Canadian Conference on Computational Geometry, Ottawa, 1990, pp. 98-101.
    • D. Halperin
      Automatic kinematic modelling of robot manipulators and symbolic generation of their inverse kinematics solutions
      Proc. 2nd International Workshop on Advances in Robot Kinematics Linz, 1990. pp. 310-317.
      [pdf] [bibtex]
    • D. Halperin
      Kinematic modelling of robot manipulators and automatic generation of their inverse kinematics solutions (in Hebrew; see English abstract at the end of the pdf file)
      M.Sc Thesis, Computer Science Department, Tel Aviv University, Tel Aviv, August 1986.
      [pdf][bibtex]

     

    Molecular Modeling

    • B.Raveh , A. Enosh , O.Furman-Schueler and D. Halperin
      Rapid sampling of molecular motions with prior information constraints
      PLoS Computational Biology, 2009
      [link] [bibtex] [project page]
    • A.Enosh,B.Raveh,O.Furman-Schueler, D. Halperin,N.Ben-Tal
      Generation, comparison and merging of pathways between protein conformations: Gating in K-channels
      Biophysical Journal, 2008
      [link] [related poster - ppt] [bibtex] [project page]
    • E. Yaffe and D. Halperin
      Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space
      Symposium on Computational Geometry, SoCG, 260-269, 2008
      [pdf] [bibtex] [project page]
    • E. Yaffe, D. Fishelovitch, H. J. Wolfson, D. Halperin, R. Nussinov
      MolAxis: a server for identification of channels in macromolecule
      Nucleic Acids Research, 36 (Web Server issue),2008, pp W210-W215
      [link] [bibtex] [project page]
    • E. Yaffe, D. Fishelovitch, H. J. Wolfson, D. Halperin, R. Nussinov
      MolAxis: efficient and accurate identification of channels in macromolecules
      Proteins: Structure, Function, and Bioinformatics. Volume 73, issue 1, 2008, Pp 72-86
      [link] [bibtex] [project page]
    • ND. Rubinstein, I. Mayrose, D. Halperin, D. Yekutieli, JM. Gershoni and T. Pupko
      Computational characterization of B-Cell epitopes
      Molecular Immunology 45, 2008, pp 3477-3489
      [link] [bibtex]
    • A. Enosh, S. J. Fleishman, N. Ben-Tal and D. Halperin
      Prediction and simulation of motion in Pairs of transmembrane alpha-helices
      Proc. 5th European Conference on Computational Biology - ECCB 2006 , Eilat, Israel, 2007.
      [link] [bibtex]
    • S. J. Fleishman, S.E. Harrington, A. Enosh, D. Halperin, C.G. Tate and N. Ben-Tal
      Quasi-symmetry in the Cryo-EM structure of EmrE provides the key to modeling its transmembrane Domain
      Journal of Molecular Biology, 364 (2006), 54-67.
      [link] [bibtex]
    • E. Eyal and D. Halperin
      Improved maintenance of molecular surfaces using dynamic graph connectivity
      Proc. 5th International Workshop on Algorithms in Bioinformatics - WABI 2005 , Mallorca, Spain, 2005, Springer LNCS, Vol. 3692.
      [pdf] [bibtex]  [project page]
    • E. Eyal and D. Halperin
      Dynamic maintenance of molecular surfaces under conformational changes
      Proc. 21st ACM Symposium on Computational Geometry , Pisa, June 2005, 45-54.
      [pdf] [bibtex] [project page]
    • A. Enosh, S.J. Fleishma, N. Ben-Tal and D. Halperin
      Assigning transmembrane segments to helics in intermediate-resolution structures
      Proc. Twelfth International Conference on Intelligent Systems for Molecular Biology (ISMB), held jointly with the Third European Conference on Computational Biology (ECCB), Glasgow, July-August, 2004, pp. 122-129.
      [pdf] [bibtex]
    • I. Lotan, F. Schwarzer, D. Halperin and J.-C. Latombe
      Algorithm and data structures for efficient energy maintenance during Monte Carlo simulation of proteins
      Journal of Computational Biology 11 (5), 2004, 902-932.
      [pdf] [bibtex]
      A preliminary and partial version, titled: Efficient maintenance and self-collision testing for kinematic chains, appeared in Proc. 18th ACM Symposium on Computational Geometry, Barcelona, 2002, pp, 43-52.
    • D. Halperin and C.R. Shelton
      A perturbation scheme for spherical arrangements with application to molecular modeling
      Computational Geometry: Theory and Applications 10 (4), 1998, 273-288. (see also the section "Robust geometric computing" above).
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 13th ACM Symposium on Computational Geometry, Nice, 1997, 183-192.
    • D. Halperin and M.H. Overmars
      Spheres, molecules, and hidden surface removal
      Computational Geometry: Theory and Applications 11 (2), 1998, 83-102.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 10th ACM Symposium on Computational Geometry, Stony Brook, 1994, 113-122.
    • P.W. Finn, D. Halperin, L. Kavraki, J.-C. Latombe, R. Motwani, C.Shelton, and S. Venkatasubramanian
      Geometric manipulation of flexible ligands
      Applied Computational Geometry: Towards geometric Engineering M.C. Lin and D. Manocha (editors), Springer 1996, (papers from the ACM Workshop on Applied Computational Geometry 1996), pp. 67-78.
      [pdf] [bibtex]
    • D. Halperin, J.-C. Latombe, and R. Motwani
      Dynamic maintenance of kinematic structures
      Algorithms for Robotic Motion and manipulation (WAFR '96), J.-P. Laumond and M. Overmars (editors), A.K. Peters, Wellesley, 1997, pp. 155-170.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 2nd Workshop on the Algorithmic Foundations of Robotics, Toulouse, 1996.

     

    Miscellaneous

    • E. Fogel, D. Halperin, and C. Weibel
      On the exact maximum complexity of Minkowski sums of convex polyhedra
      To appear in Journal of Discrete and Computational Geometry [link]
      A preliminary version appeared inACM Symposium on Computational Geometry 2007, pp. 319-326
      [pdf] [bibtex] [project page] [link]
    • H.K. Ahn, M. de Berg, P. Bose, S.W. Cheng, D. Halperin, J. Matousek, and O. Schwarzkopf
      Separating an object from its cast
      Computer-Aided Design, 34 (8), 2002, pp. 547-559.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 13th ACM Symposium on Computational Geometry, Nice, 1997, pp. 221-230.
    • B. Aronov, H. Brönimann, D. Halperin and R. Schiffenbauer
      On the number of views of polyhedral scenes
      Revised Papers of the Japanese Conference on Discrete and Computational Geometry (JCDCG 2000) , Tokai University, Japan, October 2000. Springer LNCS Vol. 2098, pp. 81-90.
      [pdf] [bibtex]
    • D. Cohen-Or, G. Fibich, D. Halperin and E. Zadicario
      Conservative visibility and strong occlusion for viewpsace partitioning of densely occluded scenes
      Eurographics '98, Computer Graphics Forum 17 (3) (1998), C243-C253.
      [pdf] [bibtex]
    • M. Charikar, D. Halperin and R.Motwani
      The dynamic servers problem
      Proc. 9th ACM Symposium on Discrete Algorithms (SODA), San Francisco, 1998, pp. 410-419.
      [pdf] [bibtex]
    • M. de Berg, D. Halperin, M.H. Overmars, J. Snoeyink and M. van Kreveld
      Efficient ray shooting and hidden surface removal
      Algorithmica 12 (1994), 30-53.
      [link] [bibtex]
      A preliminary version appeared in Proc. 7th ACM Symposium on Computational Geometry, North Conway, 1991, pp. 21-30.

     

    Surveys, Book Chapters, Book Editing

    • D. Halperin and K. Melhorn
      Algorithms
      Proc. 16th Annual European Symposium on Algorithms, 2008
      [link] [bibtex]
    • D. Halperin
      Engineering Geometric Algorithms
      In Encyclopedia of Algorithms, 2008
      [link] [bibtex]
    • E. Fogel, D. Halperin, L. Kettner, M. Teillaud, R. Wein and N. Wolpert
      Arrangements
      Effective Computational Geometry for Curves and Surfaces, Jean-Daniel Boissonnat and Monique Teillaud (eds.), Springer, Mathematics and Visualization series, 2007, Chapter 1, pp. 1-66. 
      [link] [bibtex
    • D. Halperin
      Arrangements
      CRC Handbook of Discrete and Computational Geometry, 2nd Edition, J.E. Goodman and J. O'Rourke (eds.), CRC Press, Inc., Boca Raton, FL, 2004, pp. 529-562.
      [link] [bibtex]
    • D. Halperin, L. Kavraki, and J.-C. Latombe
      Robotics
      CRC Handbook of Discrete and Computational Geometry, 2nd Edition, J.E. Goodman and J. O'Rourke (eds.), CRC Press, Inc., Boca Raton, FL, 2004, pp. 1065-1093. 
      [link] [bibtex]
    • D. Halperin
      Robust geometric computing in motion
      International Journal of Robotics Research, 21 (3), 2002, pp. 219-232. Appeared in: Algorithmic and Computational Robotics: New Dimensions (WAFR '00). B.R. Donald and K.M. Lynch and D. Rus (eds.,) A.K. Peters, Wellesley, 2001, pp. 9-22. Invited talk at WAFR 2000, Workshop on Algorithmic Foundations of Robotics , Dartmouth College, March 2000.
      [pdf] [bibtex]
    • D. Halperin, L. Kavraki, and J.-C. Latombe
      Robot algorithms
      CRC Algorithms and Theory of Computation Handbook M. Atallah (editor), CRC Press, Inc., Boca Raton, FL, 1999, Chapter 21.
      [pdf] [bibtex]
    • D. Halperin and M. Sharir
      Arrangements and their applications in robotics: Recent developments
      The Algorithmic Foundations of Robotics, K. Goldberg, D. Halperin, J.C. Latombe and R. Wilson, Eds., A.K. Peters, Boston, MA, 1995, 495-511.
      [pdf] [bibtex]
      A preliminary version appeared in Proc. 1st Workshop on the Algorithmic Foundations of Robotics, San Francisco, 1994.
    • D. Halperin
      Robot motion planning and the single cell problem in arrangements
      Journal of Intelligent and Robotic Systems 11 (1994), 45-65.
      [pdf] [bibtex]

    Books and Proceedings

    • Guy E. Blelloch, Dan Halperin
      Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, ALENEX 2010, Austin, Texas, USA, January 16, 2010
      ALENEX, SIAM 2010.
      [bibtex]
    Document Actions