Skip to main content
SpringerLink
Log in

Parallel computational geometry

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  • A. Aggarwal, J. S. Chang, and C. K. Yap (1985). Minimum area circumscribing polygons.Visual Comput.,1, pp. 112–117.

    Article  MATH  Google Scholar 

  • A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber (1986). Geometric applications of a matrix searching algorithm.Proc. 2nd ACM Symposium on Computational Geometry, pp. 285–292.

  • A. Aggarwal, B. Chazelle, L. Guibas, C. Ó'Dúnlaing, and C. K. Yap (1987). Parallel computational geometry. Robotics Report No. 115, Courant Institute, New York University. (Reported at the 26th IEEE FOCS Symposium, Portland, Oregon, 1985.)

  • M. Ajtai, J. Komlós, and E. Szemerédi (1982). AnO(n log(n)) Sorting Network.Proc. 15th ACM Symposium on Theory of Computing, pp. 1–9. Also inCombinatorica,3(1) (1983), pp. 1–19.

    Google Scholar 

  • S. Akl (1983). Parallel algorithm for convex hulls. Manuscript, Department of Computer Science, Queen's University, Kingston, Ontario.

    Google Scholar 

  • M. J. Atallah and M. T. Goodrich (1985). Efficient parallel solutions to geometric problems.Proc. 1985 IEEE Conference on Parallel Processing, pp. 411–417.

  • M. J. Atallah and M. T. Goodrich (1986). Efficient plane sweeping in parallel.Proc. 2nd Symposium on Computational Geometry, pp. 216–225.

  • M. J. Atallah, R. Cole, and M. T. Goodrich (1987). Cascading divide- and-conquer: a technique for designing parallel algorithms.Proc. 28th IEEE FOCS Symposium, pp. 151–160.

  • M. Ben-Or (1983). Lower bounds for algebraic computational trees.Proc. 15th ACM Symposium on Theory of Computing, pp. 80–86.

  • M. Ben-Or, D. Kozen, and J. Reif (1984). The complexity of elementary algebra and geometry.Proc. 16th ACM Symposium on Theory of Computing, pp. 457–464.

  • J. L. Bentley (1977). Algorithms for Klee's rectangle problems. Unpublished manuscript, CMU.

  • J. L. Bentley and D. Wood (1980). An optimal worst-case algorithm for reporting intersections of rectangles.IEEE Trans. Comput.,29, pp. 571–577.

    Article  MathSciNet  Google Scholar 

  • J. E. Boyce, D. P. Dobkin, R. L. Drysdale, and L. J. Guibas (1985). Finding extremal polygons.SIAM J. Comput.,14, pp. 134–147.

    Article  MATH  MathSciNet  Google Scholar 

  • R. P. Brent (1974). The parallel evaluation of general arithmetic expressions.J. Assoc. Comput. Mach.,21(2), pp. 201–206.

    MATH  MathSciNet  Google Scholar 

  • K. Q. Brown (1979). Voronoi diagrams from convex hulls.Inform. Process. Lett.,9(5), pp. 223–228.

    Article  MATH  Google Scholar 

  • J. S. Chang (1986). Polygon optimization problems. Ph.D. Dissertation, Robotics Report No. 78, Department of Computer Science, Courant Institute, New York University.

  • B. Chazelle (1982). A theorem on polygon cutting with applications.Proc. 23rd IEEE FOCS Symposium, pp. 339–349.

  • B. M. Chazelle (1984). Computational geometry on a systolic chip.IEEE Trans. Comput.,33, pp. 774–785.

    Article  Google Scholar 

  • B. Chazelle (1986). Reporting and counting segment intersections.J. Comput. System Sci.,32(2), pp. 156–182.

    Article  MATH  MathSciNet  Google Scholar 

  • B. Chazelle and J. Incerpi (1984). Triangulation and shape-complexity.ACM Trans. Graphics,3(2), pp. 135–152.

    Article  MATH  Google Scholar 

  • A. Chow (1980). Parallel algorithms for geometric problems. Ph.D. Dissertation, Computer Science Department, University of Illinois at Urbana-Champaign, 1980.

  • A. Chow (1981). A parallel algorithm for determining convex hulls of sets of points in two dimensions.Proc. 19th Allerton Conference on Communication, Control and Computing, pp. 214–233.

  • V. Chvátal (1975). A combinatorial theorem in plane geometry.J. Combin. Theory Ser. B,18, pp. 39–41.

    Article  MATH  Google Scholar 

  • R. Cole (1986). Parallel merge sort.Proc. 27th IEEE FOCS Symposium, pp. 511–516.

  • G. E. Collins (1975). Quantifier elimination for real closed fields by cylindrical algebraic decomposition.2nd GI Conference on Automata Theory and Formal Languages. Lecture Notes in Computer Science, Vol. 33, Springer-Verlag, Berlin, pp. 134–183.

    Google Scholar 

  • S. Cook and C. Dwork (1982). Bounds on the time for parallel RAMS to compute simple functions.Proc. 14th ACM Symposium on Theory of Computing, pp. 231–233.

  • N. Dadoun and D. G. Kirkpatrick (1987). Parallel processing for efficient subdivision search.Proc. 3rd Annual Symposium on Computational Geometry, 1987, 205–214.

    Google Scholar 

  • D. P. Dobkin and D. G. Kirkpatrick (1983). Fast detection of polyhedral intersections.Theoret. Comput. Science,27, pp. 241–253.

    Article  MATH  MathSciNet  Google Scholar 

  • H. Freeman and R. Shapira (1975). Determining the minimum-area encasing rectangle for an arbitrary closed curve.Comm. ACM,18(7), 409–413.

    Article  MATH  MathSciNet  Google Scholar 

  • L. J. Guibas and J. Stolfi (1983). Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. Proc.15th ACM Symposium on Theory of Computing, pp. 221–234. Also to appear inACM Trans. Graphics.

  • V. Klee and M. C. Laskowski (1985). Finding the smallest triangles containing a given polygon.J. Algorithms,6, pp. 457–464.

    Article  MathSciNet  Google Scholar 

  • D. Kozen and C. K. Yap (1985). Algebraic cell decomposition in NC.Proc. 26th IEEE FOCS Symposium, pp. 515–521.

  • T. Leighton (1984). Tight bounds on the complexity of parallel sorting.Proc. 16th ACM Symposium on Theory of Computing, pp. 71–80.

  • W. Lipski, Jr., and F. P. Preparata (1981). Segments, rectangles, contours.J. Algorithms,2, pp. 63–76.

    Article  MATH  MathSciNet  Google Scholar 

  • D. Nath, S. N. Maheshwari, and P. C. P. Bhatt (1981). Parallel algorithms for the convex hull in two dimensions.Proc. Conference on Analysis Problem Classes and Programming for Parallel Computing, pp. 358–372.

  • J. O'Rourke, A. Aggarwal, S. Madilla, and M. Baldwin (1986). An optimal algorithm for finding minimal enclosing triangles.J. Algorithms,7(2), 258–269.

    Article  MATH  MathSciNet  Google Scholar 

  • M. H. Overmars and J. Van Leeuwen (1981). Maintenance of configurations in the plane.J. Comput. Systems Sci.,23, pp. 166–204.

    Article  MATH  Google Scholar 

  • F. Preparata and S. J. Hong (1977). Convex hulls of finite sets of points in two and three dimensions.Comm. ACM,20, pp. 87–93.

    Article  MATH  MathSciNet  Google Scholar 

  • F. Preparata and M. I. Shamos (1985).Computational Geometry: An Introduction. Springer-Verlag, Berlin.

    Google Scholar 

  • M. I. Shamos (1977). Computational geometry. Ph.D. Dissertation, Yale University.

  • M.I. Shamos and D. Hoey (1975). Closest point problems.Proc. 16th IEEE Symposium on Foundations of Computing, pp. 151–162.

  • Y. Shiloach and U. Vishkin (1982). AnO(log(n)) parallel connectivity algorithm.J. Algorithms,3, pp. 57–67.

    Article  MATH  MathSciNet  Google Scholar 

  • R. E. Tarjan and U. Vishkin (1985). An efficient parallel biconnectivity algorithm.SIAM J. Comput., 14(4), pp. 862–874.

    Article  MATH  MathSciNet  Google Scholar 

  • G. T. Toussaint (1983). Solving geometric problems using “rotating callipers.”Proc. IEEE Melecon '83.

  • L. G. Valiant (1975). Parallelism in comparison problems.SIAM J. Comput.,4(3), pp. 348–355.

    Article  MATH  MathSciNet  Google Scholar 

  • H. Wagener (1985). Parallel computational geometry using polygon ordering. Ph.D. Thesis, Technical University of Berlin.

  • H. Wagener (1987). Optimally parallel algorithms for convex hull determination (submitted).

  • C. K. Yap (1987). What can be parallelized in computational geometry? International Workshop on Parallel Algorithms and Architecture, Humboldt University, Berlin, DDR (invited talk). Proceedings to appear.

Download references

Author information

Authors and Affiliations

  1. IBM Thomas J. Watson Research Center, 10598, Yorktown Heights, NY, USA

    A. Aggarwal

  2. Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA

    B. Chazelle

  3. Digital Equipment Corporation Systems Research Laboratories, 130 Lytton Avenue, 94301, Palo Alto, CA, USA

    L. Guibas

  4. Computer Science Department, Stanford University, 94305, Stanford, CA, USA

    L. Guibas

  5. Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012, New York, NY, USA

    C. Ó'Dúnlaing & C. Yap

  6. School of Mathematics, Trinity College, Dublin 2, Republic of Ireland

    C. Ó'Dúnlaing

Authors
  1. A. Aggarwal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Chazelle
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. L. Guibas
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. C. Ó'Dúnlaing
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. C. Yap
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The work of C. Ó'Dúnlaing and C. Yap was supported by NSF Grants DCR-84-01898 and DCR-84-01633.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aggarwal, A., Chazelle, B., Guibas, L. et al. Parallel computational geometry. Algorithmica 3, 293–327 (1988). https://doi.org/10.1007/BF01762120

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01762120

Key words

Search

Navigation