# 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

- 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. 8^{th}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 in*ACM 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]