{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:41Z","timestamp":1750307321053,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-998817CCR-0306283"],"award-info":[{"award-number":["CCR-998817CCR-0306283"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["DAAH04-96-1-0181"],"award-info":[{"award-number":["DAAH04-96-1-0181"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n            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\n            <jats:italic>P<\/jats:italic>\n            (for example, monotonicity or convexity) but that, because of errors and noise, the queries occasionally provide answers that violate\n            <jats:italic>P<\/jats:italic>\n            . Can one design a filter that modifies the query's answers so that (i) the output satisfies\n            <jats:italic>P<\/jats:italic>\n            ; (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.\n          <\/jats:p>","DOI":"10.1145\/1989727.1989728","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Online geometric reconstruction"],"prefix":"10.1145","volume":"58","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"Sandia National Labs, Livermore, Livermore, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,20]]},"reference":[{"volume-title":"Proceedings of the 8th Annual Symposium on Discrete Algorithms (SODA). 139--147","author":"Agarwal P. K.","key":"e_1_2_1_1_1","unstructured":"Agarwal , P. K. and Desikan , P. K . 1997. An efficient algorithm for terrain simplification . In Proceedings of the 8th Annual Symposium on Discrete Algorithms (SODA). 139--147 . Agarwal, P. K. and Desikan, P. K. 1997. An efficient algorithm for terrain simplification. In Proceedings of the 8th Annual Symposium on Discrete Algorithms (SODA). 139--147."},{"volume-title":"Proceedings of the 10th Annual Europeam Symposium on Algorithms (ESA). 29--41","author":"Agarwal P. K.","key":"e_1_2_1_2_1","unstructured":"Agarwal , P. K. , Har-Peled , S. , Mustafa , N. , and Wang , Y . 2002. Near-linear time approximation algorithms for curve simplification . In Proceedings of the 10th Annual Europeam Symposium on Algorithms (ESA). 29--41 . Agarwal, P. K., Har-Peled, S., Mustafa, N., and Wang, Y. 2002. Near-linear time approximation algorithms for curve simplification. In Proceedings of the 10th Annual Europeam Symposium on Algorithms (ESA). 29--41."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794269801"},{"volume-title":"Proceedings of the 8th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM). 229--236","author":"Ailon N.","key":"e_1_2_1_4_1","unstructured":"Ailon , N. , Chazelle , B. , Comandur , S. , and Liu , D . 2004a. Estimating the distance to a monotone function . In Proceedings of the 8th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM). 229--236 . Ailon, N., Chazelle, B., Comandur, S., and Liu, D. 2004a. Estimating the distance to a monotone function. In Proceedings of the 8th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM). 229--236."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_4"},{"volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 240--250","author":"Alon N.","key":"e_1_2_1_6_1","unstructured":"Alon , N. , Dar , S. , Parnas , M. , and Ron , D . 2000. Testing of clustering . In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 240--250 . Alon, N., Dar, S., Parnas, M., and Ron, D. 2000. Testing of clustering. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 240--250."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Spencer J. 2000. The Probabilistic Method 2nd Ed. Wiley.  Alon N. and Spencer J. 2000. The Probabilistic Method 2nd Ed. Wiley.","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336207"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1815293.1815294"},{"volume-title":"Proceedings of the 14th Workshop on Randomization and Computation (RANDOM). 448--461","author":"Bhattacharyya A.","key":"e_1_2_1_10_1","unstructured":"Bhattacharyya , A. , Grigorescu , E. , Jha , M. , Jung , K. , and Raskhodnikova , S . 2010. Lower bounds for local monotonicity reconstruction from transitive-closure spanners . In Proceedings of the 14th Workshop on Randomization and Computation (RANDOM). 448--461 . Bhattacharyya, A., Grigorescu, E., Jha, M., Jung, K., and Raskhodnikova, S. 2010. Lower bounds for local monotonicity reconstruction from transitive-closure spanners. In Proceedings of the 14th Workshop on Randomization and Computation (RANDOM). 448--461."},{"volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). To appear.","author":"Chakraborty S.","key":"e_1_2_1_11_1","unstructured":"Chakraborty , S. , Fischer , E. , and Matsliah , A . 2011. Query complexity lower bounds for reconstruction of codes . In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). To appear. Chakraborty, S., Fischer, E., and Matsliah, A. 2011. Query complexity lower bounds for reconstruction of codes. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS). To appear."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109689"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780620"},{"key":"e_1_2_1_14_1","first-page":"453","article-title":"Finding largest convex subsets","volume":"29","author":"Chvatal V.","year":"1980","unstructured":"Chvatal , V. and Klincsek , G. 1980 . Finding largest convex subsets . Congress. Numer. 29 , 453 -- 460 . Chvatal, V. and Klincsek, G. 1980. Finding largest convex subsets. Congress. Numer. 29, 453--460.","journal-title":"Congress. Numer."},{"volume-title":"Proceedings of 14th Annual Symposium on Discrete Algorithms (SODA). 813--822","author":"Czumaj A.","key":"e_1_2_1_15_1","unstructured":"Czumaj , A. , Ergun , F. , Fortnow , L. , Magen , A. , Newman , I. , Rubinfeld , R. , and Sohler , C . 2003. Sublinear-time approximation of Euclidean minimum spanning tree . In Proceedings of 14th Annual Symposium on Discrete Algorithms (SODA). 813--822 . Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., and Sohler, C. 2003. Sublinear-time approximation of Euclidean minimum spanning tree. In Proceedings of 14th Annual Symposium on Discrete Algorithms (SODA). 813--822."},{"volume-title":"Proceedings of 9th Annual European Symposium on Algorithms (ESA). 266--277","author":"Czumaj A.","key":"e_1_2_1_16_1","unstructured":"Czumaj , A. and Sohler , C . 2001. Property testing with geometric queries . In Proceedings of 9th Annual European Symposium on Algorithms (ESA). 266--277 . Czumaj, A. and Sohler, C. 2001. Property testing with geometric queries. In Proceedings of 9th Annual European Symposium on Algorithms (ESA). 266--277."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007386"},{"volume-title":"Proceedings of 8th Annual European Symposium on Algorithms (ESA). 155--166","author":"Czumaj A.","key":"e_1_2_1_18_1","unstructured":"Czumaj , A. , Sohler , C. , and Ziegler , M . 2000. Property testing in computational geometry . In Proceedings of 8th Annual European Symposium on Algorithms (ESA). 155--166 . Czumaj, A., Sohler, C., and Ziegler, M. 2000. Property testing in computational geometry. In Proceedings of 8th Annual European Symposium on Algorithms (ESA). 155--166."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276757"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301366"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796533"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.65"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237344"},{"volume-title":"Proceedings of 12th Annual Symposium on Discrete Algorithms (SODA). 439--447","author":"Mishra N.","key":"e_1_2_1_25_1","unstructured":"Mishra , N. , Oblinger , D. , and Pitt , L . 2001. Sublinear time approximate clustering . In Proceedings of 12th Annual Symposium on Discrete Algorithms (SODA). 439--447 . Mishra, N., Oblinger, D., and Pitt, L. 2001. Sublinear time approximate clustering. In Proceedings of 12th Annual Symposium on Discrete Algorithms (SODA). 439--447."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.51"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989728","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1989727.1989728","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:05:54Z","timestamp":1750244754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989728"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1989727.1989728"],"URL":"https:\/\/doi.org\/10.1145\/1989727.1989728","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}