Prof. Jorg-Rudiger Sack

Publications by Dr. Jörg-Rüdiger Sack

Books edited

1. Handbook of Computational Geometry,J.-R. Sack and J. Urrutia eds., Elsevier Science, January, 2000, (1027 pages).

Papers in refereed journals:

2. L. Aleksandrov, A. Maheshwari, and J.-R. Sack,"Determining Approximate Shortest Paths on Weighted Polyhedral Surfaces",Journal of the ACM, Vol. 52:1, pp. 25-53, 2005.

3. M. Lanthier, D. Nussbaum and J.-R. Sack, "A Parallel Implementation of Geometric Shortest Path Algorithms",(Special issue on High Performance Computing with Geographical Data), Parallel Computing, Vol. 29, pp. 1445-1479, 2003.

4. M. Lanthier, A. Maheshwari, and J.-R. Sack, "Approximating Shortest Paths on Weighted Polyhedral Surfaces", (Special issue on Algorithmic Engineering), Algorithmica 30(4): 527-562, 2001.

5. E. Kranankis, D. Krizanc, A. Maheshwari, J.-R. Sack, J. Urrutia, "Ray shooting from Convex Ranges", Discrete Applied Mathematics, 108:259-267, March 2001.

6. L. Aleksandrov, H. Djidjev and J.-R. Sack, "An O(n log n) algorithm for Finding a Shortest Central Link Segment", International Journal on Computational Geometry and Applications, Vol. 10:2, pp. 157-188, 2000.

7. M.D. Atkinson and J.-R. Sack, "Pop-Stacks in Parallel",Information Processing Letters, Vol. 70, pp. 63-67, 1999.

8. A. Maheshwari, and J.-R. Sack, "Simple Optimal Algorithms for Rectilinear Link Path and Polygon Separation Problems", Parallel Processing Letters, Vol. 9:1, pp. 31-42, 1999.

9. C. Hecker, D. Roytenberg, and J.-R. Sack, "System Development for Parallel Cellular Automata and its Applications", Journal of Future Generation Computer Systems, Vol. 16, Dec. 1999, pp. 235-247

10. F. Bauernöppel, E. Kranankis, D. Krizanc, A. Maheshwari,J.-R. Sack, J. Urrutia, "Planar stage graphs: characterization andapplications", Theoretical Computer Science, Vol. 175, pp. 239-255, 1997.

11. E. Kranankis, D. Krizanc, A. Maheshwari, M. Noy, J.-R. Sack, J. Urrutia, "Stage-graph representations", Discrete Applied Mathematics, Vol. 75:1, pp. 71-80, 1997.

12. R. Tamassia, P. Agarwal, N. Amato,D. Chen, D. Dobkin, R. Drysdale, S. Fortune, M. Goodrich, J. Hershberger,J. O'Rourke, F. Preparata, J.-R. Sack, S. Suri, I. Tollis, J. Vitter,and S. Whitesides,"Strategic directions in computational geometry", ACMComputing Surveys, Vol. 28:4, pp. 591-606, 1996 (report of working groupformed as part of ACM Workshop on Strategic Directions in Computing Research).

13. A. Datta, A. Maheshwari, and J.-R. Sack,"Optimal Parallel Algorithms for Direct Dominance Problems",Nordic Journal of Computing Vol. 3, pp. 72-88, 1996.

14. A. Lingas, A. Maheshwari, and J.-R. Sack, "Parallel Algorithmsfor Rectilinear Link Distance Problems", Algorithmica 14, pp. 261-289, 1995.

15. F. Dehne, B. Flach, J.-R. Sack, and N. Valiveti,"Analog Parallel Algorithms for Computational Geometry", Journal of Parallel Algorithms and Applications, Vol. 5, pp. 1-14, 1994.

16. P. Epstein and J.-R. Sack, "Generating Triangulations at Random",ACM Transaction on Modeling and Computer Simulation, Vol. 4:3, pp. 267-278, 1994.

17. M.D. Atkinson and J.-R. Sack, "Uniform Generation of Combinatorial Objects in Parallel", (research note) Journal of Parallel and Distributed Computing, 23, pp. 101-103, 1994.

18. P. Epstein, J. Kavanagh, A. Knight, J. May, T. Nguyen, J.-R. Sack, "A Workbench for Computational Geometry ", Algorithmica, 11, pp. 404-428, 1994.

19. M.D. Atkinson and J.-R. Sack, "Uniform generation of forests of restricted height", Information Processing Letters, 50, pp. 323-327, 1994.

20. L. Devroye, P. Epstein, and J.-R. Sack, "On Generating Random Intervals and Hyperrectangles", The Journal of Computational and Graphical Statistics, 2:3, pp. 291-307, 1993.

21. D. Nussbaum, and J.-R. Sack, Disassembling two-dimensionalComposite Parts via Translations, International Journal on ComputationalGeometry and Applications, 3:1, pp. 71-84, 1993.

22. M.T. Dickerson, R.L.S. Drysdale, and J.-R. Sack, "Simple Algorithms for Enumerating Interpoint Distances and Finding the k Nearest Neighbors", International Journal on Computational Geometry and Applications, 2:3, 221-239, 1992.

23. D. Djidjev, A. Lingas, and J.-R. Sack, "An O(n log n)Algorithm for Constructing a Link Center in a Simple Polygon", Discrete andComputational Geometry, 8, pp. 131-152, 1992.

24. M.D. Atkinson and J.-R. Sack, "Generating Binary Trees atRandom", Information Processing Letters, 41, pp. 21-23, 1992.

25. F. Dehne, A.-L. Hassenklover, J.-R. Sack, and N. Santoro,"Computational Geometry Algorithms for the Systolic Screen", Algorithmica,6:5, pp. 734-762, 1991.

26. J.-R. Sack, and Th. Strothotte, "A Characterization of Heapsand Its Applications", Information and Computation, 86,1, pp. 69-86, 1990.

27. J.-R. Sack, and S. Suri, "An Optimal Algorithm for DetectingWeak Visibility of a Polygon", IEEE Transactions on Computers, 39, 10, pp.1213-1219, 1990.

Chapters in Books:

28. A. Maheshwari, J.-R. Sack and H. Djidjev,"Link Distance Problems", in Handbook of Computational Geometry,J.-R. Sack and J. Urrutia eds., Elsevier Science, January, 2000, pp. 519-558.

Papers in refereed conference proceedings

29. D. Nussbaum, and J.-R. Sack, H. Ye,"Concurrent Parallel Shortest Path Computation",accepted for presentation at Parallel Computing,Malaga, Spain, September 2005.

30. E. Gervais, D. Nussbaum, and J.-R. Sack,"DynaMap: a Context Aware Dynamic Map Application",accepted for presentation at GISPlanet,Estoril, Lisbon, Portugal, May 2005.

31. A. Frankel, D. Nussbaum, and J.-R. Sack,"Floating-Point Filter for the Line Intersection Algorithm"in Proceedings GIScience, Lecture Notes in Computer Science 3234, Springer Verlag, pp. 94-105, 2004.

32. D. Nussbaum, S. Pu, and J.-R. Sack, "Fast Algorithms for Computing the Maximum Edge Cardinality Biclique in Convex Bipartite Graphs", in Proc. 2nd International Conference on Computer Science and its Applications (ICCSA-2004), pp. 255-261, 2004.

33. L. Aleksandrov, A. Maheshwari, and J.-R. Sack,"An Improved Approximation Algorithm for Computing GeometricShortest Paths", in Proc. 14th annual Symposium on the Fundamentals of Computation Theory, FCT 2003, Malmo, Sweden, August 12-15, pp. 246-257, 2003.

34. V. Audet, P. Bose, D. Nussbaum, J.-R. Sack, J. Szantos, and A. Whitehead,"Automatic Seed Detection in On-Line Portal Images for Prostate Cancer",in Proc. 2nd IASTED International Conference on Visualization, Imaging and Image Processing (VIIP), Malaga, Spain, pp. 361-366, 2002.

35. L. Aleksandrov, M. Lanthier, A. Maheshwari, and J.-R. Sack,"Approximation Algorithms for Geometric Shortest Path Problems", Proceedings, ACM Symposium on Theory of Computing, Portland, May 2000, pp. 286-295.

36. M. Lanthier, A. Maheshwari, and J.-R. Sack,"Shortest Anisotropic Paths on Terrains", in Proc. ICALP'99, Prague, LNCS 1644, pp. 524-533, 1999.

37. L. Aleksandrov, M. Lanthier, A. Maheshwari, and J.-R. Sack,"An epsilon - Approximation Algorithm for Weighted Shortest Pathson Polyhedral Surfaces", in Proc. SWAT'98, Stockholm, LNCS 1432, pp. 11-22, 1998.

38. A. Maheshari, Patrick Morin and J.-R. Sack, "Progressive TINs: Algorithms and Applications", in Proc. ACM-GIS'97, 5th International Workshopon Adavances in Geographic Information Systems, pp. 24-29, 1997.

39. M. Lanthier, A. Maheshwari, and J.-R. Sack, "Approximating Weighted Shortest Paths onPolyhedral Surfaces", in Proc. 13th annual ACM Symposium on Computational Geometry, pp. 274-283, 1997.

40. D. Hutchinson, A. Maheshwari, J.-R. Sack, and R. Velicescu,"Early Experiences in Implementing the Buffer Tree",Proc. Workshop on Algorithm Engineering, 1997.

41. D. Hutchinson, M. Lanthier, A. Maheshwari, D. Nussbaum,D. Roytenberg, and J.-R. Sack, "Parallel Neighbourhood Modeling",(full conference version), Proc. ACM GIS, pp. 26-34, 1997.

42. D. Hutchinson, L. Küttner, M. Lanthier, A. Maheshwari, D. Nussbaum,D. Roytenberg, and J.-R. Sack, "Parallel Neighbourhood Modeling",research summary,Proc. 8th Annual ACM Symposium on Parallel Algorithmsand Architectures (SPAA'96), Padua, Italy, pp. 204-207, 1996.

43. F. Bauernöppel, E. Kranankis, D. Krizanc, A. Maheshwari, M. Noy, J.-R. Sack, J. Urrutia, "Optimal shooting: characterizations and applications", Proc. 22nd ICALP, Szeged, Hungary, LNCS Vol. 944, Springer Verlag, pp. 220-231, 1995.

44. A. Datta, A. Maheshwari, and J.-R. Sack, "Optimal CREW-PRAM algorithms for direct dominance problems", Proc. 1st European Sypmosium on Algorithms'93, Bad Honnef, Germany, LNCS Vol. 726, Springer Verlag, pp. 109-120, 1993.

45. A. Lingas, A. Maheshwari, and J.-R. Sack, "Parallel Algorithmsfor Rectilinear Link Distance Problems", Proc. 7th International Parallel Processing Symposium, IPPS '93, Newport Beach, pp. 65-72, 1993.

46. P. Epstein, A. Knight, J. May, T. Nguyen, J.-R. Sack, "AWorkbench for Computational Geometry (WOCG)", demonstrated at 6thAnnualSymposium on Computational Geometry (by invitation of PC committee), Berkeley, CA, June 6-8, 1990; abstract inproceedings p.370.

47. D. Nussbaum, and J.-R. Sack, "Dissassembling two-dimensionalComposite Parts via Translations", Proc. Int. Workshop on Optimal Algorithms,Varna, Bulgaria, June 1989, Lecture Notes in Computer Science, Springer Verlag (invited paper), pp. 153-167, 1989.

48. F. Dehne, A.-L. Hassenklover, and J.-R. Sack, "Computing theConfiguration Space For a Robot on a Mesh-Of-Processors", Proc. 1989International Conf. on Parallel Processing, Vol. III, Chicago, pp. 40-48, 1989.

49. D. Djidjev, A. Lingas, and J.-R. Sack, "An O(n log n)Algorithm for Constructing a Link Center in a Simple Polygon", Proc.STACS'89,Paderborn, F.R. of Germany, Lecture Notes in Computer Science, Vol. 349, eds.B. Monien, R. Cori, pp. 96-108, 1989.

50. F. Dehne, and J.-R. Sack, "Parallel Computational Geometry: ASurvey", Parcella '88, Berlin, Lecture Notes in Computer Science, Vol. 342,eds. G. Wolf, T. Legendi, U. Schendel, pp. 73-88 (invited paper), 1988.

51. F. Dehne, I. Stojmenovic, and J.-R. Sack, "A Note onDetermining the 3-Dimensional Convex Hull of a Set of Points on a Mesh ofProcessors", Proc. Scandinavian Workshop on Algorithm Theory, Halmstad,Sweden, Lecture Notes in Computer Science, Vol. 318, eds. R. Karlsson and A.Lingas, pp. 154 - 162, 1988.

52. O. Nurmi, and J.-R. Sack, "Separating a Polyhedron by OneTranslation from a Set of Obstacles", Proc. Workshop on Graph-TheoreticConcepts in Computer Science, Amsterdam, The Netherlands, Lecture Notes inComputer Science, Vol. 344, ed. J. van Leeuwen, pp. 202-212, 1988.

53. J.-R. Sack, and S. Suri, "An Optimal Algorithm for DetectingWeak Visibility of a Polygon", Proc.STACS'88, Bordeaux, France, Lecture Notesin Computer Science, Vol. 294, eds. R. Cori, M. Wirsing, pp. 312-322, 1988.

54. Th. Strothotte and J.-R. Sack, "Knowledge Aquisition usingDiagrams", Proc. 3rd IFIP Conference on Man-Machine Systems, Oulo, Finland,1988.

55. F. Dehne, A. Hassenklover, J.-R. Sack, and N. Santoro,"Parallel Visibility on a Mesh-Connected Parallel Computer", ProcInternational Conference on Parallel Processing and Applications 87, Aquilla,Italy, North Holland, pp. 203-210, 1987.

56. C. Levcopoulos, A. Lingas, and J.-R. Sack, "Nearly OptimalHeuristics for Binary Search Trees with Geometric Generalizations", Proc ICALP'87 , Karlsruhe, Germany, Lecture Notes in Computer Science 267, Springer,Berlin Heidelberg New York Tokyo, pp. 376-385, 1987.

57. W. Lenhart, R. Pollack, J.-R. Sack, R. Seidel, M.Sharir, S. Suri, G.T. Toussaint, S. Whitesides and C.K. Yap, "Computing theLink Center of a Simple Polygon", Proc 3rd ACM Conference on ComputationalGeometry, Waterloo, pp. 1-10, 1987.

58. F. Dehne, J.-R. Sack, and N. Santoro, "Computing on aSystolic Screen: Hulls, Contours and Applications", Proc Conference onParallel Architectures and Languages Europe (Parle), Eindhoven, TheNetherlands, June 1987, Lecture Notes in Computer Science 258, editors J.W. deBakker, A.J. Nijman, P.C. Trealeaven, Springer, Berlin Heidelberg New YorkTokyo, pp. 121-133, 1987.

59. A. Hasham and J.-R. Sack, "A Note on Lower Bounds for Min-MaxHeaps", Proc 24 rd Allerton Conference on Communication, Control andComputing, Urbana-Champaign, Ill., pp. 306-307 (summary), 1986.

60. J. A. Dean, A. Lingas, and J.-R. Sack, "Recognizing Polygons:or How to Eavesdrop", Proc 24 rd Allerton Conference on Communication, Controland Computing, Urbana-Champaign, Ill., pp. 324-333, 1986.

61. F. Dehne, and J.-R. Sack, "Separability of Sets of PolygonsThrough Single Translations", Proc WG'87, Bernried, FRG, Lecture Notes inComputer Science 246, Springer, Berlin Heidelberg New York Tokyo, pp.237-251, 1987.

Non-refereed contributions

62. A. Maheshwari P. Morin J.-R. Sack, "A Framework for Multiresolution Modelling", in Workshop: Multi-Resolution Representation of 3D Geometry for Progressive Transmission, Visualization'98, Raleigh, Oct. 1998.

63. M. Ghodsi and J.-R. Sack"A Coarse Grained Parallel Solution to Terrain Simplification",accepted for presentation at CCCG'98, Montreal, 1998.

64. L. Aleksandrov, M.Lanthier, A. Maheshwari, J.-R. Sack"An 1#1-Approximation Algorithm for Weighted Shortest PathQueries on Polyhedral Surfaces", Proc. 14th EURO'CG, Barcelona, pp. 19-21, 1998.

65. D. Dubrule, P. Morin, J.-R. Sack,"A Parallel Cartographic Modelling System: design, implementationand performance", Proc. GIS'97, Vancouver, pp. 16-20, 1997.

66. D. Roytenberg, J.-R. Sack,"A Simulator for the Alex-AVX Parallel Multi-Computer"in Proc. HPCS '96 Conference, paper No. 48, Ottawa, 1996.

67. F. Dehne, H. Djidjev, J.-R. Sack, "An optimal PRAM Algorithm for Convex Embedding of Planar Graphs", International Workshop on Graph Drawing andTopological Graph Algorithms, Paris, 1993.

68. F. Dehne, B. Flach, J.-R. Sack, and N. Valiveti, "AnalogParallel Computational Geometry", Proc. of the 4th CCCG, pp. 143-153, 1992.

69. P. Epstein and J.-R. Sack, "Generating Triangulations atRandom", Proc. of the 4th CCCG, pp. 305-310, 1992.

70. D. Nussbaum and J.-R. Sack, "Translation Separability ofPolyhedra", 1st Canadian Conference on Computation Geometry, Montrèal, Canada,abstract in Proc., 1989.

Proceedings(edited):

71. Proc. 9th Workshop on Algorithms and Data Structures, eds.F. Dehne, A. Lopez-Ortiz, and J.-R. Sack, Lecture Notes in Computer Science, Vol. 3608, Springer Verlag, 2005.

72. Proc. 8th Workshop on Algorithms and Data Structures, eds.F. Dehne, J.-R. Sack, and M. Smid, Lecture Notes in Computer Science, Vol. 2748, Springer Verlag, 2003.

73. Proc. 7th Workshop on Algorithms and Data Structures, eds.F. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, Lecture Notes in Computer Science, Vol. 2125, Springer Verlag, 2001.

74. Proc. 6th Workshop on Algorithms and Data Structures, eds.F. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, Lecture Notes in Computer Science, Vol. 1663, Springer Verlag, 1999.

75. Proc. 5th Workshop on Algorithms and Data Structures, eds.A. Rau-Chaplin, F. Dehne, J.-R. Sack, and R. Tamassia, Lecture Notes in Computer Science, Vol. 1272 , Springer Verlag, 1997.

76. Proc. 8th Canadian Conference on Computational Geometry, eds.F. Fiala, E. Kranakis and J.-R. Sack, in International Informatics Series 5,1996.

77. Proc. 4th Workshop on Algorithms and Data Structures, eds.S. Akl, F. Dehne, J.-R. Sack, and N. Santoro, Lecture Notes in Computer Science,Vol. 955, Springer Verlag, 1995.

78. Proc. 3rd Workshop on Algorithms and Data Structures, eds. F. Dehne, J.-R. Sack, N. Santoro, and S. Whitesides, Lecture Notes in Computer Science, Vol. 709, Springer Verlag, 1993.

79. Proc. Workshop on Algorithms and Data Structures, eds.F. Dehne, J.-R. Sack, and N. Santoro, Lecture Notes in Computer Science, Vol.519, Springer Verlag, 1991.

80. Proc. Workshop on Algorithms and Data Structures, eds.F. Dehne, J.-R. Sack, and N. Santoro, Lecture Notes in Computer Science, Vol.382, Springer Verlag, 1989.

Videos(refereed and edited):

81. M. Lanthier, A. Maheshwari, and J.-R. Sack, "Approximating Weighted Shortest Paths onPolyhedral Surfaces", in 6th annual Video Review of Computational Geometry,13th ACM SoCG, video ed. J. Snoeyink; abstract in Proc. 13th annual ACM Symposium on Computational Geometry, pp. 485-486, 1997 (illustrating the paper in same proceedings).

82. P. Epstein, J. Kavanagh, A. Knight, J.-R. Sack, "A Workbenchfor Computational Geometry", in Animation Geometric Algorithms: A VideoReview, video eds. M. Brown and J. Hershberger, presented at the 8th ACMConf. on Computational Geometry, Berlin 1992.

Videos(other):

83. D. Roytenberg and J.-R. Sack,"Spatial Modelling in Parallel",an Educational Video Production, 1997.

84. D. Roytenberg and J.-R. Sack,"An Introduction to the ALEX Informatique Parallel Computer",Educational Video Production, 1996.