Computational geometry

ABSTRACT

A compendium of thirty previously published open problems in computational geometry is presented

REFERENCES

• 1: N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336207]
• 2: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
• 3: Pankaj K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, SIAM Journal on Computing, v.21 n.3, p.540-570, June 1992 [doi>10.1137/0221035]
• 4: G. Albers, L. J. Guibas, J. S. B. Mitchell, and T. Roos. Voronoi diagrams of moving points. Internat. J. Comput. Geom. Appl., 8:365-380, 1998.
• 5: Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Linear-time triangulation of a simple polygon made easier via randomization, Proceedings of the sixteenth annual symposium on Computational geometry, p.201-212, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336206]
• 6: Thomas Auer , Martin Held, Heuristics for the Generation of Random Polygons, Proceedings of the 8th Canadian Conference on Computational Geometry, p.38-43, August 12-15, 1996
• 7: E. M. Arkin, M. Held, J. S. B. Mitchell, and s. S. Skiena. Hamiltonian triangulations for fast rendering. Visual Comput., 12(9): 429-444, 1996.
• 8: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 9: Pankaj K. Agarwal , Subhash Suri, Surface Approximation and Geometric Partitions, SIAM Journal on Computing, v.27 n.4, p.1016-1035, Aug. 1998 [doi>10.1137/S0097539794269801]
• 10: Pankaj K. Agarwal , Micha Sharir, Pipes, cigars, and kreplach: the union of Minkowski sums in three dimensions, Proceedings of the fifteenth annual symposium on Computational geometry, p.143-153, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304960]
• 11: P. K. Agarwal and M. Sharir. Davenport-Schinzel sequences and their geometric applications. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 1-47. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
• 12: P. K. Agarwal and M. Sharir. Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions. Discrete Comput. Geom. 24(4): 645-685, 2000.
• 13: P. K. Agarwal and K. R. Varadarajan. Approximating monotone polygonal curves using the uniform metric. Discrete Comput. Geom., 23, 2000. to appear.
• 14: Marshall Bern , Erik D. Demaine , David Eppstein , Eric Kuo , Andrea Mantler , Jack Snoeyink, Ununfoldable polyhedra with convex faces, Computational Geometry: Theory and Applications, v.24 n.2, p.51-62, February 2003 [doi>10.1016/S0925-7721(02)00091-3]
• 15: M. Bern, D. Eppstein, P. K. Agarwal, N. Amenta, P. Chew, T. Dey, D. P. Dobkin, H. Edelsbrunner, C. Grimm, L. J. Guibas, J. Harer, J. Hass, A. Hicks, C. K. Johnson, G. Lerman, D. Letscher, P. Plassmann, E. Sedgeick, J. Snoeyink, J. Weeks, C. Yap, and D. Zorin. Emerging challenges in computational topology, 1999. Report on an NSF Workshop on computational Topology, June 11-12, Miami Beach, FL
• 16: H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom., 14: 263-279, 1995.
• 17: Gerth Stølting Brodal , Riko Jacob, Dynamic Planar Convex Hull with Optimal Query Time, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.57-70, July 05-07, 2000
• 18: M. Bern and A. Sahai. Pushing disks together — The continuous-motion case. Discrete Comput. Geom., 20: 299-514, 1998.
• 19: J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom., 19(4): 473-484, 1998.
• 20: Vasilis Capoyleas, On the area of the intersection of disks in the plane, Computational Geometry: Theory and Applications, v.6 n.6, p.393-396, Nov. 1996 [doi>10.1016/0925-7721(95)00029-1]
• 21: W. S. Chan and F. Chin. Approximation of polygonal curves with minimum number of line segments or minimum error. Internat. J. Comput. Geom. Appl., 6:59-77, 1996.
• 22: B. Chazelle. Tight bounds on the stabbing number of spanning trees in Euclidean space. Report CS-TR-155-88, Dept. Comput. Sci., Princeton Univ., Princeton, NJ, 1988.
• 23: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 24: T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom., 16:369-387, 1996.
• 25: Bernard Chazelle, A Faster Deterministic Algorithm for Minimum Spanning Trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.22, October 19-22, 1997
• 26: Timothy M. Chan, Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.92, October 17-18, 1999
• 27: L. Paul Chew, Near-quadratic bounds for the L1 Voronoi diagram of moving points, Computational Geometry: Theory and Applications, v.7 n.1-2, p.73-80, Jan. 1997 [doi>10.1016/0925-7721(95)00044-5]
• 28: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 29: Siu-Wing Cheng , Kam-Hing Lee, Quadtree Decomposition, Steiner Triangulation, and Ray Shooting, Proceedings of the 9th International Symposium on Algorithms and Computation, p.367-376, December 14-16, 1998
• 30: T. K. Dey. Improved bounds on planar k-sets and related problems. Discrete Comput. Geom., 19:373-382, 1998.
• 31: Gautam Das , Michael T. Goodrich, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees, Computational Geometry: Theory and Applications, v.8 n.3, p.123-137, Aug. 1997 [doi>10.1016/S0925-7721(97)00006-0]
• 32: Matthew T. Dickerson , Scott A. McElfresh , Mark Montague, New algorithms and empirical findings on minimum weight triangulation heuristics (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.238-247, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220305]
• 33: M. E. Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput., 13:31-45, 1984.
• 34: Vladimir Estivill-Castro , Joseph O'Rourke , Jorge Urrutia , Dianna Xu, Illumination of polygons with vertex lights, Information Processing Letters, v.56 n.1, p.9-13, Oct. 13, 1995 [doi>10.1016/0020-0190(95)00129-Z]
• 35: D. Eppstein. Approximating the minimum weight Steiner triangulation. Discrete Comput. Geom., 11:163-191, 1994.
• 36: David Eppstein, Linear complexity hexahedral mesh generation, Proceedings of the twelfth annual symposium on Computational geometry, p.58-67, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237237]
• 37: H. Edelsbrunner , F. P. Preparata , D. B. West, Tetrahedrizing point sets in three dimensions, Journal of Symbolic Computation, v.10 n.3-4, p.335-347, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80068-5]
• 38: A. Efrat and M. Sharir. On the complexity of the union of fat objects in the plane. Discrete Comput. Geom., 23:171-189, 2000.
• 39: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 40: Dima Grigoriev , Marek Karpinski , Friedhelm Meyer auf der Heide , Roman Smolensky, A lower bound for randomized algebraic decision trees, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.612-619, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238011]
• 41: Anka Gajentaan , Mark H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications, v.5 n.3, p.165-185, Oct. 1995 [doi>10.1016/0925-7721(95)00022-2]
• 42: John Hershberger , Jack Snoeyink, An O(nlogn) implementation of the Douglas-Peucker algorithm for line simplification, Proceedings of the tenth annual symposium on Computational geometry, p.383-384, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178097]
• 43: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 44: Barry Joe, Construction of three-dimensional Delaunay triangulations using local transformations, Computer Aided Geometric Design, v.8 n.2, p.123-142, May 1991 [doi>10.1016/0167-8396(91)90038-D]
• 45: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 46: L. G. Khachiyan. Polynomial algorithm in linear programming. U. S. S. R. Comput. Math. And Math. Phys., 20:53-72, 1980.
• 47: S. Kapoor, S. N. Maheshwari, and J. S. B, Mitchell. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane Discrete Comput. Geom., 18:377-383, 1997.
• 48: V. Koltun (Machtey Award Co-winner), Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.56, October 14-17, 2001
• 49: Christos Levcopoulos , Drago Krznaric, Quasi-greedy triangulations approximating the minimum weight triangulation, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.392-401, January 28-30, 1996, Atlanta, Georgia, United States
• 50: László Lovász, On Conway's thrackle conjecture, Proceedings of the eleventh annual symposium on Computational geometry, p.147-151, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220295]
• 51: Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
• 52: Scott A. Mitchell, A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.465-476, February 22-24, 1996
• 53: J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633-701. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
• 54: J. S. B. Mitchell, G. Rote, and G. Woeginer. Minimum-link paths among obstacles in the plane. Algorithmica, 8:431-459, 1992
• 55: Joseph S. B. Mitchell , Subhash Suri, Separation and approximation of polyhedral objects, Computational Geometry: Theory and Applications, v.5 n.2, p.95-114, Sept. 1995 [doi>10.1016/0925-7721(95)00006-U]
• 56: J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16:498-516, 1996.
• 57: Joseph O'Rourke, Computational geometry column 18, ACM SIGACT News, v.24 n.1, p.20-25, Winter 1993 [doi>10.1145/152992.152994]
• 58: Joseph O'Rourke, Folding and Unfolding in Computational Geometry, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.258-266, December 09-12, 1998
• 59: Joseph O'Rourke , Ileana Streinu, Vertex-edge pseudo-visibility graphs: characterization and recognition, Proceedings of the thirteenth annual symposium on Computational geometry, p.119-128, June 04-06, 1997, Nice, France [doi>10.1145/262839.262915]
• 60: J. Pach , Ido Safruti , Micha Sharir, The union of congruent cubes in three dimensions, Proceedings of the seventeenth annual symposium on Computational geometry, p.19-28, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378598]
• 61: Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
• 62: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 63: Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]
• 64: M. Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput. Geom. , 12:327-345, 1994.
• 65: G. C. Shephard. Convex polytopes with convex nets. Math. Proc. Camb. Phil. Soc., 78:389-403, 1975.
• 66: Jack Snoeyink, Point location, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 67: Géza Tóth, Point sets with many k-sets, Proceedings of the sixteenth annual symposium on Computational geometry, p.37-42, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336171]
• 68: Csaba D. T'oth, A note on binary plane partitions, Proceedings of the seventeenth annual symposium on Computational geometry, p.151-156, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378652]
• 69: J. Urrutia. Art gallery and illumination problems. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry pages 973-1027, North-Holland, 2000.
• 70: P. M. Vaidya, Geometry helps in matching, SIAM Journal on Computing, v.18 n.6, p.1201-1225, Dec. 1989 [doi>10.1137/0218080]
• 71: E. Welzl. Geometric graphs with small stabbing numbers: Combinatorics and applications. In Proc 9th Internat. Conf. Fund. Comput. Theory, Lecture Notes Comput. Sci., Springer-Verlag, 1993.
• 72: Chong Zhu , Gopalakrishnan Sundaram , Jack Snoeyink , Joseph S. B. Mitchell, Generating random polygons with given vertices, Computational Geometry: Theory and Applications, v.6 n.5, p.277-290, Sept. 1996 [doi>10.1016/0925-7721(95)00031-3]

INDEX TERMS

General Terms:
Theory