{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:11:05Z","timestamp":1725459065592},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540198932"},{"type":"electronic","value":"9783540393375"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/bfb0035535","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T15:09:36Z","timestamp":1138201776000},"page":"855-862","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["k-violation linear programming"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Roos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,23]]},"reference":[{"key":"80_CR1","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"K.L. Clarkson and P.W. Shor, Applications of random sampling in computational geometry, II, Discrete & Comput. Geometry, Vol. 4, 1989, pp. 387\u2013421","journal-title":"Discrete & Comput. Geometry"},{"issue":"4","key":"80_CR2","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R. Cole","year":"1989","unstructured":"R. Cole, J. Salowe, W. Steiger and E. Szemer\u00e9di, An Optimal-Time Algorithm for Slope Selection, SIAM J. Comp., Vol. 18, No. 4, 1989, pp 792\u2013810","journal-title":"SIAM J. Comp."},{"key":"80_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs in Computer Science, Springer, Berlin, 1987"},{"key":"80_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner and P. M\u00fccke, A Technique to Cope with Degenerate Cases in Geometric Algorithms, ACM Trans. Computer Graphics, Vol. 9, 1990, pp 66\u2013104","journal-title":"ACM Trans. Computer Graphics"},{"issue":"1","key":"80_CR5","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and E. Welzl, Constructing Belts in Two-Dimensional Arrangements with Applications, SIAM J. Comput., Vol. 15, No. 1. 1986, pp 271\u2013284","journal-title":"SIAM J. Comput."},{"key":"80_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(91)90177-J","volume":"39","author":"J. Matou\u0161ek","year":"1991","unstructured":"J. Matou\u0161ek, Randomized Optimal Algorithm for Slope Selection, Info. Proc. Letters, Vol. 39, 1991, pp 183\u2013187","journal-title":"Info. Proc. Letters"},{"key":"80_CR7","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, M. Sharir and E. Welzl, A Subexponential Bound for Linear Programming, Proc. 8th Annual ACM Symp. on Computational Geometry, Berlin, 1992, pp 1\u20138","DOI":"10.1145\/142675.142678"},{"key":"80_CR8","unstructured":"K. Mulmuley, On Levels in Arrangements and Voronoi Diagrams, Discrete & Comput. Geom., to appear"},{"key":"80_CR9","doi-asserted-by":"crossref","unstructured":"R. Seidel, Linear Programming and Convex Hulls Made Easy, Proc. 6th ACM Symposium on Computational Geometry, Berkeley, California, 1990, pp 211\u2013215","DOI":"10.1145\/98524.98570"},{"key":"80_CR10","unstructured":"M. Sharir and E. Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proc. Symposium on Theoretical Aspects of Computer Science STACS'92, LNCS 577, pp 569\u2013579"}],"container-title":["Lecture Notes in Control and Information Sciences","System Modelling and Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0035535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T19:48:16Z","timestamp":1578512896000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0035535"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540198932","9783540393375"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0035535","relation":{},"ISSN":["0170-8643","1610-7411"],"issn-type":[{"type":"print","value":"0170-8643"},{"type":"electronic","value":"1610-7411"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"23 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}