{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:02:46Z","timestamp":1648512166416},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,1,10]],"date-time":"2013-01-10T00:00:00Z","timestamp":1357776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1007\/s00453-012-9738-z","type":"journal-article","created":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T20:31:51Z","timestamp":1357763511000},"page":"410-430","source":"Crossref","is-referenced-by-count":0,"title":["Outlier Respecting Points Approximation"],"prefix":"10.1007","volume":"69","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,10]]},"reference":[{"key":"9738_CR1","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1287\/opre.49.5.771.10607","volume":"49","author":"R.K. Ahuja","year":"2001","unstructured":"Ahuja, R.K., Orlin, J.B.: Inverse optimization. Oper. Res. 49, 771\u2013783 (2001)","journal-title":"Oper. Res."},{"key":"9738_CR2","first-page":"164","volume-title":"Proc. of the Second International Conference on Knowledge Discovery and Data Mining","author":"A. Arning","year":"1996","unstructured":"Arning, A., Agrawal, R., Raghavan, P.: A linear method for deviation detection in large databases. In: Proc. of the Second International Conference on Knowledge Discovery and Data Mining, pp.\u00a0164\u2013169 (1996)"},{"key":"9738_CR3","volume-title":"Outliers in Statistical Data","author":"V. Barnett","year":"1994","unstructured":"Barnett, V., Lewis, T.: Outliers in Statistical Data. Wiley, New York (1994)"},{"key":"9738_CR4","first-page":"88","volume-title":"Proc. of the 4th Latin American Symposium on Theoretical Informatics","author":"M. Bender","year":"2000","unstructured":"Bender, M., Farach-Colton, M.: The LCA problem revisited. In: Proc. of the 4th Latin American Symposium on Theoretical Informatics, pp.\u00a088\u201394 (2000)"},{"key":"9738_CR5","first-page":"617","volume-title":"Proc. of the 43rd IEEE Symposium on Foundations of Computer Science","author":"G. Brodal","year":"2002","unstructured":"Brodal, G., Jacob, R.: Dynamic planar convex hull. In: Proc. of the 43rd IEEE Symposium on Foundations of Computer Science, pp.\u00a0617\u2013626 (2002)"},{"key":"9738_CR6","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01585693","volume":"53","author":"D. Burton","year":"1992","unstructured":"Burton, D., Toint, Ph.L.: On an instance of the inverse shortest paths problem. Math. Program. 53, 45\u201361 (1992)","journal-title":"Math. Program."},{"issue":"3","key":"9738_CR7","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02712874","volume":"16","author":"T.M. Chan","year":"1996","unstructured":"Chan, T.M.: Output-sensitive results on convex hulls and extreme points, and related problems. Discrete Comput. Geom. 16(3), 369\u2013387 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9738_CR8","first-page":"570","volume-title":"Proc. of 43rd IEEE Symposium on Foundations of Computer Science","author":"T.M. Chan","year":"2002","unstructured":"Chan, T.M.: Low-dimensional linear programming with violations. In: Proc. of 43rd IEEE Symposium on Foundations of Computer Science, pp.\u00a0570\u2013579 (2002)"},{"issue":"1\u20134","key":"9738_CR9","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF01762115","volume":"3","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: An algorithm for segment-dragging and its implementation. Algorithmica 3(1\u20134), 205\u2013221 (1988)","journal-title":"Algorithmica"},{"key":"9738_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/978-3-642-10631-6_24","volume-title":"Proc. of the 20th International Symposium on Algorithms and Computation","author":"D.Z. Chen","year":"2009","unstructured":"Chen, D.Z., Wang, H.: Approximating points by a piecewise linear function: I. In: Proc. of the 20th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol.\u00a05878, pp.\u00a0224\u2013233. Springer, Berlin (2009)"},{"key":"9738_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/978-3-642-10631-6_25","volume-title":"Proc. of the 20th International Symposium on Algorithms and Computation","author":"D.Z. Chen","year":"2009","unstructured":"Chen, D.Z., Wang, H.: Approximating points by a piecewise linear function: II. Dealing with outliers. In: Proc. of the 20th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol.\u00a05878, pp.\u00a0234\u2013243. Springer, Berlin (2009)"},{"issue":"1","key":"9738_CR12","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/S0377-2217(00)00023-0","volume":"130","author":"J. D\u00edaz-B\u00e1nez","year":"2001","unstructured":"D\u00edaz-B\u00e1nez, J., Mesa, J.: Fitting rectilinear polygonal curves to a set of points in the plane. Eur. J. Oper. Res. 130(1), 214\u2013222 (2001)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"9738_CR13","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D.P. Dobkin","year":"1985","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6(3), 381\u2013392 (1985)","journal-title":"J. Algorithms"},{"key":"9738_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/BFb0032047","volume-title":"Proc. of the 17th International Colloquium on Automata, Languages and Programming","author":"D.P. Dobkin","year":"1990","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: Determining the separation of preprocessed polyhedra\u2014a unified approach. In: Proc. of the 17th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol.\u00a0443, pp.\u00a0400\u2013413. Springer, Berlin (1990)"},{"issue":"1","key":"9738_CR15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M. Dyer","year":"1984","unstructured":"Dyer, M.: Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput. 13(1), 31\u201345 (1984)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9738_CR16","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1142\/S0218195996000186","volume":"6","author":"H. Everett","year":"1996","unstructured":"Everett, H., Robert, J.-M., van Kreveld, M.: An optimal algorithm for the (\u2264k)-levels and with applications to separation and transversal problems. Int. J. Comput. Geom. Appl. 6(3), 247\u2013261 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9738_CR17","first-page":"442","volume-title":"Proc. of the 16th Annual European Symposium on Algorithms","author":"H. Fournier","year":"2008","unstructured":"Fournier, H., Vigneron, A.: Fitting a step function to a point set. In: Proc. of the 16th Annual European Symposium on Algorithms, pp.\u00a0442\u2013453 (2008)"},{"key":"9738_CR18","first-page":"135","volume-title":"Proc. of the 16th Annual ACM Symposium on Theory of Computing","author":"H. Gabow","year":"1984","unstructured":"Gabow, H., Bentley, J., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. of the 16th Annual ACM Symposium on Theory of Computing, pp.\u00a0135\u2013143 (1984)"},{"key":"9738_CR19","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1145\/380752.380841","volume-title":"Proc. of the 33rd Annual ACM Symposium on Theory of Computing","author":"S. Guha","year":"2001","unstructured":"Guha, S., Koudas, N., Shim, K.: Data streams and histograms. In: Proc. of the 33rd Annual ACM Symposium on Theory of Computing, pp.\u00a0471\u2013475 (2001)"},{"issue":"7","key":"9738_CR20","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1109\/TKDE.2007.1039","volume":"19","author":"S. Guha","year":"2007","unstructured":"Guha, S., Shim, K.: A note on linear time algorithms for maximum error histograms. IEEE Trans. Knowl. Data Eng. 19(7), 993\u2013997 (2007)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"9738_CR21","first-page":"300","volume-title":"Proc. of the 30th International Conference on Very Large Data Bases","author":"S. Guha","year":"2004","unstructured":"Guha, S., Shim, K., Woo, J.: Rehist: Relative error histogram construction algorithms. In: Proc. of the 30th International Conference on Very Large Data Bases, pp.\u00a0300\u2013311 (2004)"},{"key":"9738_CR22","first-page":"32","volume-title":"Proc. of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Hershberger","year":"1991","unstructured":"Hershberger, J., Suri, S.: Offline maintenance of planar configurations. In: Proc. of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a032\u201341 (1991)"},{"issue":"3","key":"9738_CR23","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1023\/B:JOCO.0000038914.26975.9b","volume":"8","author":"C. Heuberger","year":"2004","unstructured":"Heuberger, C.: Inverse combinatorial optimization: a survey on problems, methods, and results. J.\u00a0Comb. Optim. 8(3), 329\u2013361 (2004)","journal-title":"J.\u00a0Comb. Optim."},{"key":"9738_CR24","first-page":"380","volume-title":"Proc. of the 13th International Conference on Knowledge Discovery and Data Mining","author":"P. Karras","year":"2007","unstructured":"Karras, P., Sacharidis, D., Mamoulis, N.: Exploiting duality in summarization with deterministic guarantees. In: Proc. of the 13th International Conference on Knowledge Discovery and Data Mining, pp.\u00a0380\u2013389 (2007)"},{"issue":"1","key":"9738_CR25","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput. 12(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"key":"9738_CR26","first-page":"382","volume-title":"Proc. of the 24th International Conference on Very Large Data Bases","author":"E. Knorr","year":"1998","unstructured":"Knorr, E., Ng, R.: Algorithms for mining distance-based outliers in large datasets. In: Proc. of the 24th International Conference on Very Large Data Bases, pp.\u00a0382\u2013403 (1998)"},{"issue":"1","key":"9738_CR27","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02570713","volume":"14","author":"J. Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: On geometric optimization with few violated constraints. Discrete Comput. Geom. 14(1), 365\u2013384 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9738_CR28","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31(1), 114\u2013127 (1984)","journal-title":"J. ACM"},{"key":"9738_CR29","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(78)90051-8","volume":"7","author":"D. Muller","year":"1978","unstructured":"Muller, D., Preparata, F.P.: Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7, 217\u2013236 (1978)","journal-title":"Theor. Comput. Sci."},{"key":"9738_CR30","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1145\/358746.358758","volume":"24","author":"J. O\u2019Rourke","year":"1981","unstructured":"O\u2019Rourke, J.: An on-line algorithm for fitting straight lines between data ranges. Commun. ACM 24, 574\u2013578 (1981)","journal-title":"Commun. ACM"},{"issue":"2","key":"9738_CR31","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F.P. Preparata","year":"1977","unstructured":"Preparata, F.P., Hong, S.J.: Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20(2), 87\u201393 (1977)","journal-title":"Commun. ACM"},{"issue":"2","key":"9738_CR32","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1145\/335191.335437","volume":"29","author":"S. Ramaswamy","year":"2000","unstructured":"Ramaswamy, S., Rastogi, R., Shim, K.: Efficient algorithms for mining outliers from large data sets. ACM SIGMOD Rec. 29(2), 427\u2013438 (2000)","journal-title":"ACM SIGMOD Rec."},{"issue":"2","key":"9738_CR33","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(94)00134-0","volume":"52","author":"T. Roos","year":"1994","unstructured":"Roos, T., Widmayer, P.: k-violation linear programming. Inf. Process. Lett. 52(2), 109\u2013114 (1994)","journal-title":"Inf. Process. Lett."},{"key":"9738_CR34","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00454-001-0005-3","volume":"26","author":"M. Sharir","year":"2001","unstructured":"Sharir, M., Smorodinsky, S., Tardos, G.: An improved bound for k-sets in three dimensions. Discrete Comput. Geom. 26, 195\u2013204 (2001)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9738_CR35","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1023\/A:1022429905385","volume":"25","author":"J. Zhang","year":"2003","unstructured":"Zhang, J., Lin, Y.: Computation of the reverse shortest-path problem. J. Glob. Optim. 25(3), 243\u2013261 (2003)","journal-title":"J. Glob. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9738-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9738-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9738-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:11Z","timestamp":1559137511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9738-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,10]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["9738"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9738-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,10]]}}}