Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Math HOME

.......................

Faculty

.......................

Publications of Herbert Edelsbrunner    :chronological  alphabetical  combined  bibtex listing:

Books

  1. H. Edelsbrunner, Geometry and Topology for Mesh Generation (2001), Cambridge Univ. Press, England
  2. H. Edelsbrunner, Algorithms in Combinatorial Geometry (1995), Springer-Verlag, Heidelberg, Germany, 1987 (Translated into Japanese by Hiroshi Imai and Keiko Imai, Kyoritsu Shuppan, Japan.)

Papers Published

  1. H. Edelsbrunner, 180 wrapped tubes, J. Univ. Comput. Sci., vol. 7 (2001), pp. 379-399
  2. H.-L. Cheng, T. K. Dey, J. Sullivan and H. Edelsbrunner, Dynamic skin triangulation, The Micha Sharir Birthday Issue, eds.P. Agarwal, D. Halperin and R. Pollack, Discrete Comput. Geom., vol. 25 (2001), pp. 525-568
  3. H.-L. Cheng, P. Fu and H. Edelsbrunner, Shape space from deformation, Comput. Geom. Theory Appl., vol. 19 (2001), pp. 191-204
  4. S.-W. Cheng, P. Fu, P. Lam and H. Edelsbrunner, Design and analysis of planar shape deformation, Comput. Geom. Theory Appl., vol. 19 (2001), pp. 205-218
  5. H. Edelsbrunner, Triangulations and meshes in computational geometry, Acta Numerica (2000), pp. 133-213
  6. D. R. Grayson and H. Edelsbrunner, Edgewise subdivision of a simplex, Discrete Comput. Geom., vol. 24 (2000), pp. 707-719
  7. S.-W. Cheng, T. K. Dey, M. A. Facello, S.-H. Teng and H. Edelsbrunner, Sliver exudation, J. Assoc. Comput. Mach., vol. 47 (2000), pp. 273-277
  8. R. Waupotitsch and H. Edelsbrunner, Adaptive simplicial grids from cross-sections of monotone complexes, Internat. J. Comput. Geom. Appl., vol. 10 (2000), pp. 267-284
  9. H. Edelsbrunner, Spielereien mit Kreisen und Kugeln. Zum Thema Form und Verformung, in Zur Kunst des formalen Denkens,153-171, edited by R. E. Burkard, W. Maas und P. Weibel (2000), Passagen Verlag, Wien, Austria
  10. T. K. Dey, S. Guha, D. V. Nekhayev and H. Edelsbrunner, Topology preserving edge contraction, Publ. Inst. Math. (Beograd) (N. S.), vol. 66 (1999), pp. 23-45
  11. H. Edelsbrunner, Deformable smooth surface design, Discrete Comput. Geom., vol. 21 (1999), pp. 87-115
  12. T. K. Dey, S. Guha and H. Edelsbrunner, Computational topology, in Advances in Discrete and Computational Geometry, 109-143, edited by B. Chazelle, J. E. Goodman and R. Pollack (1999), Contemporary Mathematics 223, AMS, Providence,
  13. J. Liang, C. Woodward and H. Edelsbrunner, Anatomy of protein pockets and cavities: measurement of binding site geometry and implications for ligand design, Protein Science, vol. 7 (1998), pp. 1884-1897
  14. J. Liang, P. Fu, P. V. Sudhakar, S. Subramaniam and H. Edelsbrunner, Analytic shape computation of macromolecules II: inaccessible cavities in proteins, Proteins: Structure, Function, and Genetics, vol. 33 (1998), pp. 18-29
  15. J. Liang, P. Fu, P. V. Sudhakar, S. Subramaniam and H. Edelsbrunner, Analytic shape computation of macromolecules I: molecular area and volume through alpha shape, Proteins: Structure, Function, and Genetics, vol. 33 (1998), pp. 1-17
  16. M. Facello, J. Liang and H. Edelsbrunner, On the definition and the construction of pockets in macromolecules, Discrete Appl. Math., vol. 88 (1998), pp. 83-102
  17. U. Axen and H. Edelsbrunner, Auditory Morse analysis of triangulated manifolds, in Mathematical Visualization, 223-236, edited by H.-C. Hege and K. Polthier (1998), Springer-Verlag, Berlin, Germany
  18. H. Edelsbrunner, Geometry for modeling biomolecules, in Robotics: The Algorithmic Perspective, The Third Workshop on the Algorithmic Foundations of Robotics, 265-277, edited by P. Agarwal, L. Kavraki and M. Mason (1998), A. K. Peters, Natick, Massachusetts
  19. R. Waupotitsch and H. Edelsbrunner, A combinatorial approach to cartograms, J. Comput. Geom. Theory Appl., vol. 7 (1997), pp. 343-360
  20. E. A. Ramos and H. Edelsbrunner, Inclusion-exclusion complexes for pseudodisk collections, Discrete Comput. Geom., vol. 17 (1997), pp. 287-306
  21. P. Valtr, E. Welzl and H. Edelsbrunner, Cutting dense point sets in half, Discrete Comput. Geom., vol. 17 (1997), pp. 243-255
  22. N. R. Shah and H. Edelsbrunner, Triangulating topological spaces, Internat. J. Comput. Geom. Appl., vol. 7 (1997), pp. 365-378
  23. N. Akkiraju, P. Fu, J. Qian and H. Edelsbrunner, Viewing geometric protein structures from inside a cave, IEEE Comput. Graphics Appl., vol. 16 (1996), pp. 58-61
  24. N. Akkiraju and H. Edelsbrunner, Triangulating the surface of a molecule, Discrete Appl. Math., vol. 71 (1996), pp. 5-22
  25. N. R. Shah and H. Edelsbrunner, Incremental topological ipping works for regular triangulations, Algorithmica, vol. 15 (1996), pp. 223-241
  26. B. Chazelle, L. J. Guibas, M. Sharir, J. Stolfi and H. Edelsbrunner, Lines in space: combinatorics and algorithms, Algorithmica, vol. 15 (1996), pp. 428-447
  27. C. J. A. Delfinado and H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Comput. Aided Geom. Design, vol. 17 (1995), pp. 771-784
  28. H. Edelsbrunner, The union of balls and its dual shape, in Laszlo Fejes Toth Festschrift, edited by I. Barany and J. Pach, Discrete Comput. Geom., vol. 13 (1995), pp. 415-440
  29. B. Chazelle, M. Grigni, L. J. Guibas, M. Sharir, E. Welzl and H. Edelsbrunner, Improved bounds on weak " -nets for convex sets, Discrete Comput. Geom., vol. 13 (1995), pp. 1-15
  30. T. R. Dey and H. Edelsbrunner, Counting triangle crossings and halving planes, Discrete Comput. Geom., vol. 12 (1994), pp. 281-289
  31. E. P. Mucke and H. Edelsbrunner, Three-dimensional alpha shapes, ACM Trans. Graphics, vol. 13 (1994), pp. 43-72
  32. B. Chazelle, M. Grigni, L. J. Guibas, J. E. Hershberger, M. Sharir, J. Snoeyink and H. Edelsbrunner, Ray shooting in polygons using geodesic triangulations, Algorithmica, vol. 12 (1994), pp. 54-68
  33. B. Chazelle, L. J. Guibas, M. Sharir and H. Edelsbrunner, Algorithms for bichromatic line segment problems and polyhedral terrains, Algorithmica, vol. 11 (1994), pp. 116-132
  34. B. Chazelle, L. J. Guibas, J. E. Hershberger, R. Seidel, M. Sharir and H. Edelsbrunner, Selecting heavily covered points, SIAM J. Comput., vol. 23 (1994), pp. 1138-1151
  35. H. Edelsbrunner, Computational geometry, in Chapter 1 in Current Trends in Theoretical Computer Science, Essays and Tutorials, 1-48, edited by G. Rozenberg and A. Salomaa (1993), World Scientific, Singapore
  36. B. Chazelle, L. J. Guibas, M. Sharir and H. Edelsbrunner, Diameter, width, closest line pair, and parametric searching, Discrete Comput. Geom., vol. 10 (1993), pp. 183-196
  37. T. S. Tan and H. Edelsbrunner, An upper bound for conforming Delaunay triangulations, Discrete Comput. Geom., vol. 10 (1993), pp. 197-213
  38. T. S. Tan and H. Edelsbrunner, A quadratic time algorithm for the minmax length triangulation, SIAM J. Comput., vol. 22 (1993), pp. 527-551
  39. M. Bern, D. Eppstein, S. Mitchell, T. S. Tan and H. Edelsbrunner, Edge insertion for optimal triangulations, Discrete Comput. Geom., vol. 10 (1993), pp. 47-65
  40. B. Chazelle, L. J. Guibas, M. Sharir, J. Snoeyink and H. Edelsbrunner, Computing a face in an arrangement of line segments and related problems, SIAM J. Comput., vol. 22 (1993), pp. 1286-1302
  41. R. Seidel, M. Sharir and H. Edelsbrunner, On the zone theorem for hyperplane arrangements, SIAM J. Comput., vol. 22 (1993), pp. 418-429
  42. H. Edelsbrunner, Geometric algorithms, in Chapter 2.9 in Handbook of Convex Geometry, 699-735, edited by P. Gruber and J. Wills (1992), North-Holland
  43. A. Aggarwal, P. Raghavan, P. Tiwari and H. Edelsbrunner, Optimal time bounds for some proximity problems in the plane, Inform. Process. Lett., vol. 42 (1992), pp. 55-60
  44. T. S. Tan, R. Waupotitsch and H. Edelsbrunner, An O log time algorithm for the minmax angle triangulation, SIAM J. Sci. Stat. Comput., vol. 13 (1992), pp. 994-1008
  45. B. Aronov, L. J. Guibas, M. Sharir and H. Edelsbrunner, The number of edges of many faces in a line segment arrangement, Combinatorica, vol. 12 (1992), pp. 261-274
  46. B. Chazelle, L. J. Guibas, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink and H. Edelsbrunner, Counting and cutting cycles of lines and rods in space, Computational Geometry: Theory and Applications, vol. 1 (1992), pp. 305-323
  47. L. J. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir and H. Edelsbrunner, Arrangements of curves in the plane - topology, combinatorics, and algorithms, Theoret. Comput. Sci., vol. 92 (1992), pp. 319-336
  48. B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, J. Assoc. Comput. Mach., vol. 39 (1992), pp. 1-54
  49. H. Edelsbrunner, Lines in space - a collection of results, in Discrete and Computational Geometry, 77-93, DIAMCS Series in Discrete Mathematics and Theoretical Computer Science, vol. 6, edited by R. Pollack and W. Steiger (1991)
  50. M. Sharir and H. Edelsbrunner, A hyperplane incidence problem with applications to counting distances, in Applied Geometry and Discrete Mathematics The Victor Klee Festschrift, 253-263, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, edited by P. Gritzmann and B. Sturmfels (1991)
  51. B. Aronov, B. Chazelle, L. J. Guibas, M. Sharir, R. Wenger and H. Edelsbrunner, Points and triangles in the plane and halving planes in space, Discrete Comput. Geom., vol. 6 (1991), pp. 435-442
  52. P. K. Agarwal, O. Schwarzkopf, E. Welzl and H. Edelsbrunner, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete Comput. Geom., vol. 6 (1991), pp. 407-422
  53. W. Shi and H. Edelsbrunner, An O log time algorithm for the three-dimensional convex hull problem, SIAM J. Comput., vol. 20 (1991), pp. 259-269
  54. B. Chazelle, L. J. Guibas, M. Sharir and H. Edelsbrunner, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoret. Comput. Sci., vol. 84 (1991), pp. 77-105
  55. P. Hajnal and H. Edelsbrunner, A lowerbound on thenumber of unit distances between the vertices of a convex polygon, J. Combin. Theory Ser. A, vol. 56 (1991), pp. 312-316
  56. H. Edelsbrunner, Corrigendum, J. Comput. System Sci., vol. 42 (1991), pp. 249-251
  57. D. P. Dobkin, C. K. Yap and H. Edelsbrunner, Probing convex polytopes, in Autonomous Robot Vehicles, 328-341, edited by I. J. Cox and G. T. Wilfong (1990), Springer-Verlag, New York
  58. M. H. Overmars, E. Welzl, I. Ben-Arroyo Hartman, J. A. Feldman and H. Edelsbrunner, Ranking intervals under visibility constraints, Internat. J. Comput. Math., vol. 34 (1990), pp. 129-144
  59. F. P. Preparata, D. B. West and H. Edelsbrunner, Tetrahedrizing point sets in three dimensions, J. Symbolic Comput., vol. 10 (1990), pp. 335-347
  60. L. J. Guibas, M. Sharir and H. Edelsbrunner, The complexity ofmany cells in arrangements of planes and related problems, Discrete Comput. Geom., vol. 5 (1990), pp. 197-216
  61. L. J. Guibas, M. Sharir and H. Edelsbrunner, The complexity and construction of many faces in arrangements of lines and of segments, Discrete Comput. Geom., vol. 5 (1990), pp. 161-196
  62. K. L. Clarkson, L. G. Guibas, M. Sharir, E. Welzl and H. Edelsbrunner, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom., vol. 5 (1990), pp. 99-160
  63. H. Edelsbrunner, An acyclicity theorem for cell complexes in d dimensions, Combinatorica, vol. 10 (1990), pp. 251-260
  64. D. L. Souvaine and H. Edelsbrunner, Computing least median of squares regression lines and guided topological sweep, J. Amer. Statist. Assoc., vol. 85 (1990), pp. 115-119
  65. D. P. Dobkin, M. H. Overmars and H. Edelsbrunner, Searching for empty convex polygons, Algorithmica, vol. 5 (1990), pp. 561-571
  66. E. P. Mucke and H. Edelsbrunner, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Trans. Graphics, vol. 9 (1990), pp. 66-104
  67. A. D. Robison, X. J. Shen and H. Edelsbrunner, Covering convex sets with non-overlapping polygons, Discrete Math., vol. 81 (1990), pp. 153-164
  68. M. Sharir and H. Edelsbrunner, The maximum number of ways to stab n convex nonintersecting sets in the plane is 2 n, Discrete Comput. Geom., vol. 5 (1990), pp. 35-42
  69. L. J. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl and H. Edelsbrunner, Implicitly representing arrangements of lines or segments, Discrete Comput. Geom., vol. 4 (1989), pp. 433-466
  70. L. J. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink and H. Edelsbrunner, On arrangements of Jordan arcs with three intersections per pair, Discrete Comput. Geom., vol. 4 (1989), pp. 523-539
  71. F. F. Yao, D. P. Dobkin, M. S. Paterson and H. Edelsbrunner, Partitioning space for range queries, SIAM J. Comput., vol. 18 (1989), pp. 371-384
  72. N. Hasan, R. Seidel, X. J. Shen and H. Edelsbrunner, Circles through two points that always enclose many points, Geometriae Dedicata, vol. 32 (1989), pp. 1-12
  73. H. Edelsbrunner, The upper envelope of piecewise linear functions: tight bounds on the number of faces, Discrete Comput. Geom., vol. 4 (1989), pp. 337-343
  74. L. J. Guibas, M. Sharir and H. Edelsbrunner, The upper envelope of piecewise linear functions: algorithms and applications, Discrete Comput. Geom., vol. 4 (1989), pp. 311-336
  75. G. Rote, E. Welzl and H. Edelsbrunner, Testing the necklace condition for shortest tours and optimal factors in the plane, Theoret. Comput. Sci., vol. 66 (1989), pp. 157-180
  76. B. Chazelle, L. J. Guibas and H. Edelsbrunner, The complexity of cutting complexes, Discrete Comput. Geom., vol. 4 (1989), pp. 139-182
  77. S. S. Skiena and H. Edelsbrunner, On the number of furthest neighbour pairs in a point set, Amer. Math. Monthly, vol. 96 (1989), pp. 614-618
  78. L. J. Guibas and H. Edelsbrunner, Topologically sweeping an arrangement, J. Comput. System Sci., vol. 38 (1989), pp. 165-194
  79. S. S. Skiena and H. Edelsbrunner, Probing convex polygons with x-rays, SIAM J. Comput., vol. 17 (1988), pp. 870-882
  80. F. P. Preparata and H. Edelsbrunner, Minimum polygonal separation, Inform. and Comput., vol. 77 (1988), pp. 218-232
  81. X. J. Shen and H. Edelsbrunner, A tight lower bound on the size of visibility graphs, Inform. Process. Lett., vol. 26 (1987), pp. 61-64
  82. B. Chazelle and H. Edelsbrunner, Linear space data structures for two types of range search, Discrete Comput. Geom., vol. 2 (1987), pp. 113-126
  83. B. Chazelle and H. Edelsbrunner, An improved algorithm for constructing k -order Voronoi diagrams, IEEE Trans. Comput., vol. C-36 (1987), pp. 1349-1354
  84. M. H. Overmars and H. Edelsbrunner, Zooming by repeated range detection, Inform. Process. Lett., vol. 24 (1987), pp. 413-417
  85. D. P. Dobkin and H. Edelsbrunner, Space searching for intersecing objects, J. Algorithms, vol. 8 (1987), pp. 348-361
  86. R. Waupotitsch and H. Edelsbrunner, Computing a ham-sandwich cutintwo dimensions, J. Symbolic Comput., vol. 2 (1986), pp. 171-178
  87. R. Seidel and H. Edelsbrunner, Voronoi diagrams and arrangements, Discrete Comput. Geom., vol. 1 (1986), pp. 25-44
  88. G. Stockl and H. Edelsbrunner, The number of extreme pairs of finite point-sets in Euclidean spaces, J. Combin. Theory Ser. A, vol. 43 (1986), pp. 344-349
  89. H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, vol. 1 (1986), pp. 93-109
  90. D. Haussler and H. Edelsbrunner, The complexity of cells in three-dimensional arrangements, Discrete Math., vol. 60 (1986), pp. 139-146
  91. J. O'Rourke, R. Seidel and H. Edelsbrunner, Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., vol. 15 (1986), pp. 341-363
  92. J. W. Jaromczyk and H. Edelsbrunner, How often can you see yourself in a convex configuration of mirrors?, Congressus Numerantium, vol. 53 (1986), pp. 193-200
  93. G. Haring, D. Hilbert and H. Edelsbrunner, Rectangular point location in d dimensions with applications, Comput. J., vol. 29 (1986), pp. 76-82
  94. L. J. Guibas, J. Stolfi and H. Edelsbrunner, Optimal point location in a monotone subdivision, SIAM J. Comput., vol. 15 (1986), pp. 317-340
  95. E. Welzl and H. Edelsbrunner, Halfplanar range search in linear space and O( n query time, Inform. Process. Lett., vol. 23 (1986), pp. 289-293
  96. E. Welzl and H. Edelsbrunner, On the maximal number of edges of many faces in an arrangement, J. Combin. Theory Ser. A, vol. 41 (1986), pp. 159-166
  97. E. Welzl and H. Edelsbrunner, Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput., vol. 15 (1986), pp. 271-284
  98. B. Chazelle and H. Edelsbrunner, Optimal solutions for a class of point retrieval problems, J. Symbolic Comput., vol. 1 (1985), pp. 47-56
  99. W. H. E. Day and H. Edelsbrunner, Investigation of proportional link linkage clustering methods, J. Classification, vol. 2 (1985), pp. 239-254
  100. H. A. Maurer and H. Edelsbrunner, Finding extreme points in three dimensions and solving the post-oÆce problem in the plane, Inform. Process. Lett., vol. 21 (1985), pp. 39-47
  101. M. H. Overmars and H. Edelsbrunner, Batched dynamic solutions to decomposable searching problems, J. Algorithms, vol. 6 (1985), pp. 515-542
  102. E. Welzl and H. Edelsbrunner, On the number of line separations of a finite set in the plane, J. Combin. Theory Ser. A, vol. 38 (1985), pp. 15-29
  103. H. Edelsbrunner, Computing the extreme distances between two convex polygons, J. Algorithms, vol. 6 (1985), pp. 213-224
  104. H. Edelsbrunner, Finding transversals for sets of simple geometric figures, Theoret. Comput. Sci., vol. 35 (1985), pp. 55-69
  105. W. H. E. Day and H. Edelsbrunner, EÆcient algorithms for agglomerative hierarchical clustering methods, J. Classification, vol. 1 (1984), pp. 7-24
  106. M. H. Overmars, R. Seidel and H. Edelsbrunner, Some methods of computational geometry applied to computer graphics, Comput. Vision, Graphics, Image Process, vol. 28 (1984), pp. 92-108
  107. J. O'Rourke, E. Welzl and H. Edelsbrunner, Stationing guards in rectilinear art galleries, Comput. Vision, Graphics, Image Process, vol. 28 (1984), pp. 167-176
  108. F. Aurenhammer and H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition, vol. 17 (1984), pp. 251-257
  109. J. v. Leeuwen, Th. Ottmann, D. Wood and H. Edelsbrunner, Computing the connected components of simple rectilinear geometrical objects in d -space, RAIRO Inform. Theor., vol. 18 (1984), pp. 171-183
  110. M. H. Overmars, D. Wood and H. Edelsbrunner, Graphics in Flatland: a case study, in Advances in Computing Research, Vol. 1, 35-59, edited by F. P. Preparata (1983), Jai Press, London
  111. W. Bucher and H. Edelsbrunner, On expected-and worst-case segment trees, in Advances in Computing Research Vol. 1, 109-125, edited by F. P. Preparata (1983), Jai Press, London
  112. D. G. Kirkpatrick, R. Seidel and H. Edelsbrunner, On the shape of a set of points in the plane, IEEE Trans. Inform. Theory, vol. IT-29 (1983), pp. 551-559
  113. H. Edelsbrunner, A new approach to rectangle intersections - part II, Internat. J. Comput. Math., vol. 13 (1983), pp. 221-229
  114. H. Edelsbrunner, A new approach to rectangle intersections - part I, Internat. J. Comput. Math., vol. 13 (1983), pp. 209-219
  115. H. A. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl, D. Wood and H. Edelsbrunner, Stabbing line segments, BIT, vol. 22 (1982), pp. 274-281
  116. M. H. Overmars and H. Edelsbrunner, On the equivalence of some rectangle problems, Inform. Process. Lett., vol. 14 (1982), pp. 124-127
  117. D. G. Kirkpatrick, H. A. Maurer and H. Edelsbrunner, Polygonal intersection searching, Inform. Process. Lett., vol. 14 (1982), pp. 74-79
  118. H. A. Maurer and H. Edelsbrunner, A space-optimal solution of general region location, Theoret. Comput. Sci., vol. 16 (1981), pp. 329-336
  119. H. A. Maurer and H. Edelsbrunner, On the intersection of orthogonal objects, Inform. Process. Lett., vol. 13 (1981), pp. 177-181

Papers Accepted

  1. D. Letscher, A. Zomorodian and H. Edelsbrunner, Topological persistence and simplification, Discrete Comput. Geom. (2002)
  2. A. Zomorodian and H. Edelsbrunner, Fast software for box intersections, Internat. J. Comput. Geom. Appl. (2002)

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
Mathematics Home | Arts & Sciences | Duke University