Online geometric reconstruction

ABSTRACT

We investigate a new class of geometric problems based on the idea of online error correction. Suppose one is given access to a large geometric dataset though a query mechanism; for example, the dataset could be a terrain and a query might ask for the coordinates of a particular vertex or for the edges incident to it. Suppose, in addition, that the dataset satisfies some known structural property P (eg, monotonicity or convexity) but that, because of errors and noise, the queries occasionally provide answers that violate P. Can one design a filter that modifies the query's answers so that (i) the output satisfies P; (ii) the amount of data modification is minimized? We provide upper and lower bounds on the complexity of online reconstruction for convexity in 2D and 3D.

REFERENCES

• 1: Alon, N., Spencer, J. The probabilistic method, John Wiley, 2nd edition, 2000.
• 2: Pankaj K. Agarwal , Pavan K. Desikan, An efficient algorithm for terrain simplification, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.139-147, January 05-07, 1997, New Orleans, Louisiana, United States
• 3: Pankaj K. Agarwal , Torben Hagerup , Rahul Ray , Micha Sharir , Michiel H. M. Smid , Emo Welzl, Translating a Planar Object to Maximize Point Containment, Proceedings of the 10th Annual European Symposium on Algorithms, p.42-53, September 17-21, 2002
• 4: Agarwal, P.K., Har-Peled, S., Mustafa, N., Wang, Y. Near-linear time approximation algorithms for curve simplification, to appear in Algorithmica.
• 5: Agarwal, P.K., Matoušek, J. Dynamic half-space searching and its applications, Algorithmica 14 (1995), 325--345.
• 6: 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]
• 7: Ailon, N., Chazelle, B., Comandur, S., Liu, D. Estimating the distance to a monotone function, Proc. RANDOM (2004), 229--236.
• 8: Ailon, N., Chazelle, B., Comandur, S., Liu, D. Property preserving data reconstruction, Proc. ISAAC (2004), 16--27.
• 9: N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
• 10: 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]
• 11: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 12: Bernard Chazelle , Ding Liu , Avner Magen, Sublinear geometric algorithms, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780620]
• 13: Chvatal, V., Klincsek, G. Finding largest convex subsets, Congressus Numerantium: 29 (1980), 453--460.
• 14: Artur Czumaj , Funda Ergün , Lance Fortnow , Avner Magen , Ilan Newman , Ronitt Rubinfeld , Christian Sohler, Sublinear-time approximation of Euclidean minimum spanning tree, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 15: Artur Czumaj , Christian Sohler, Property Testing with Geometric Queries, Proceedings of the 9th Annual European Symposium on Algorithms, p.266-277, August 28-31, 2001
• 16: Artur Czumaj , Christian Sohler, Estimating the weight of metric minimum spanning trees in sublinear-time, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007386]
• 17: Artur Czumaj , Christian Sohler , Martin Ziegler, Property Testing in Computational Geometry, Proceedings of the 8th Annual European Symposium on Algorithms, p.155-166, September 05-08, 2000
• 18: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 19: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.259-268, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276757]
• 20: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 21: Piotr Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.154, October 17-18, 1999
• 22: Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
• 23: Lipton, R.J., Tarjan, R.E. A separator theorem for planar graphs, SIAM Journal on Applied Mathematics 36 (1979), 177--189.
• 24: Lipton, R.J., Tarjan, R.E. Applications of a planar separator theorem, SIAM J. Comput. 9 (1980), 615--627.
• 25: Kurt Mehlhorn , Stefan Näher , Thomas Schilz , Stefan Schirra , Michael Seel , Raimund Seidel , Christian Uhrig, Checking geometric programs or verification of geometric structures, Proceedings of the twelfth annual symposium on Computational geometry, p.159-165, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237344]
• 26: Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
• 27: Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
computational geometry, sublinear algorithms