{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T06:32:31Z","timestamp":1791268351361,"version":"4.1.0"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: given a set S of n points sampled from a bivariate function f(x,y) and an input parameter $\\eps &gt; 0$, compute a piecewise-linear function $\\Sigma(x,y)$ of minimum complexity (that is, an xy-monotone polyhedral surface, with a minimum number of vertices, edges, or faces) such that $| \\Sigma(x_p, y_p) \\; - \\; z_p | \\:\\:\\leq\\:\\: \\eps$ for all $(x_p, y_p, z_p) \\in S$. We give hardness evidence for this problem, by showing that a closely related problem is NP-hard. The main result of our paper is a polynomial-time approximation algorithm that computes a piecewise-linear surface of size O(K\n                    <jats:sub>o<\/jats:sub>\n                    log K\n                    <jats:sub>o<\/jats:sub>\n                    ), where K\n                    <jats:sub>o<\/jats:sub>\n                    is the complexity of an optimal surface satisfying the constraints of the problem.\n                  <\/jats:p>\n                  <jats:p>The technique developed in our paper is more general and applies to several other problems that deal with partitioning of points (or other objects) subject to certain geometric constraints. For instance, we get the same approximation bound for the following problem arising in machine learning: given n \"red\" and m \"blue\" points in the plane, find a minimum number of pairwise disjoint triangles such that each blue point is covered by some triangle and no red point lies in any of the triangles.<\/jats:p>","DOI":"10.1137\/s0097539794269801","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1016-1035","source":"Crossref","is-referenced-by-count":57,"title":["Surface Approximation and Geometric Partitions"],"prefix":"10.1137","volume":"27","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0724033"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0722020"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"E. Arkin, H. Meijer, J. Mitchell, D. Rappaport, and S. Skiena,\n                      Decision trees for geometric models\n                      , in Symp. on Comput. Geom. 9th, 1993, pp. 369\u2013378.","DOI":"10.1145\/160985.161167"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(88)90013-1"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758854"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Kenneth Clarkson, Algorithms for polytope covering and approximation, Lecture Notes in Comput. Sci., Vol. 709, Springer, Berlin, 1993, 246\u201325294k:68186","DOI":"10.1007\/3-540-57155-8_252"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(91)90071-O"},{"key":"R9","unstructured":"S. Fekete,\n                      Several Hardness Results on Problems of Point Separation and Line Stabbing\n                      , Tech. Report, Dept. of Applied Math. and Stats., SUNY Stony Brook, New York, 1993."},{"key":"R10","first-page":"85","volume":"35","author":"Fowler R.","year":"1981","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"I. Ihm and B. Naylor,\n                      Piecewise linear approximations of digitized space curves with applications\n                      , in Scientific Visual. of Physical Phenomena, Springer\u2010Verlag, New York, 1991, pp. 545\u2013569.","DOI":"10.1007\/978-4-431-68159-5_30"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37422"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00006-U"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187806"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90007-Y"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/21.97458"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/142920.134010"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/15886.15906"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/70.88124"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/142920.134008"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794269801","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:03Z","timestamp":1787335923000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794269801"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794269801"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794269801","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}