{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T17:54:53Z","timestamp":1662573293216},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1007\/bf02574379","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T08:11:43Z","timestamp":1174551103000},"page":"241-261","source":"Crossref","is-referenced-by-count":36,"title":["Helly-type theorems and Generalized Linear Programming"],"prefix":"10.1007","volume":"12","author":[{"given":"N.","family":"Amenta","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1994,9,1]]},"reference":[{"key":"BF02574379_CR1","unstructured":"N. Amenta. Finding a line transversal of axial objects in three dimensionsProceeding of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pages 66\u201371."},{"key":"BF02574379_CR2","unstructured":"B. Aronov, J. E. Goodman, R. Pollack, and R. Wenger. There is no Hadwiger number for line transversals in higher dimensions. Unpublished manuscript, cited in [GPW], Theorem 2.9."},{"key":"BF02574379_CR3","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0166-218X(90)90127-X","volume":"27","author":"D. Avis","year":"1990","unstructured":"D. Avis and M. Doskas. Algorithms for high dimensional stabbing problems,Discrete Applied Mathematics, vol. 27 (1990), pages 39\u201348.","journal-title":"Discrete Applied Mathematics"},{"key":"BF02574379_CR4","unstructured":"D. Avis and M. E. Houle. Computational aspects of Helly\u2019s theorem and its relatives,Proceedings of the Third Canadian Conference on Computational Geometry, 1991, pages 11\u201314."},{"key":"BF02574379_CR5","unstructured":"B. Chazelle and J. Matou\u0161ek. On linear-time deterministic algorithms for optimization problems in fixed dimension,Proceeding of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pages 281\u2013290."},{"key":"BF02574379_CR6","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small, Manuscript, 1990. An earlier version appeared inProceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pages 452\u2013455.","DOI":"10.1109\/SFCS.1988.21961"},{"key":"BF02574379_CR7","series-title":"Proceedings of the Symposium on Pure Mathematics","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1090\/pspum\/007\/0157289","volume-title":"Helly\u2019s theorem and its relatives","author":"L. Danzer","year":"1963","unstructured":"L. Danzer, B. Gr\u00fcnbaum, and V. Klee Helly\u2019s theorem and its relatives,Proceedings of the Symposium on Pure Mathematics, vol. 7, 1963, pages. 101\u2013180. American Mathematical Society, Providence, RI."},{"issue":"no. 1","key":"BF02574379_CR8","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1137\/0613003","volume":"13","author":"J. Demmel","year":"1992","unstructured":"J. Demmel. The componentwise distance to the nearest singular matrix,SIAM Journal of Matrix Analysis and Applications, vol. 13, no. 1 (1992), pages 10\u201319.","journal-title":"SIAM Journal of Matrix Analysis and Applications"},{"key":"BF02574379_CR9","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1137\/0215052","volume":"15","author":"M. Dyer","year":"1986","unstructured":"M. Dyer. On a multidimensional search technique and its application to the Euclidean one-center problem,SIAM Journal on Computing vol. 15 (1986), pages 725\u2013738.","journal-title":"SIAM Journal on Computing"},{"key":"BF02574379_CR10","doi-asserted-by":"crossref","unstructured":"M. Dyer. A class of convex programs with applications to computational geometry,Proceedings of the 8th Annual Symposium on Computational Geometry, 1992, pages 9\u201315.","DOI":"10.1145\/142675.142681"},{"key":"BF02574379_CR11","volume-title":"Handbook of Convex Geometry","author":"J. Eckhoff","year":"1993","unstructured":"J. Eckhoff. Helly, Radon- and Carathody type theorems, inHandbook of Convex Geometry, P. M. Gruber and J. M. Willis, eds., Chapter 2.1. Elsevier Science, Amsterdam, 1993."},{"key":"BF02574379_CR12","doi-asserted-by":"crossref","unstructured":"P. Egyed and R. Wenger. Stabbing pairwise disjoint translates in linear time,Proceedings of the 5th Annual Symposium on Computational Geometry, 1989, pages 364\u2013369.","DOI":"10.1145\/73833.73873"},{"key":"BF02574379_CR13","unstructured":"J.E. Goodman, R. Pollack, and R. Wenger, Geometric transversal theory, inNew Trends in Discrete and Computational Geometry. Springer-Verlag, New York (to appear)."},{"key":"BF02574379_CR14","doi-asserted-by":"crossref","first-page":"607","DOI":"10.2307\/2034254","volume":"12","author":"B. Gr\u00fcnbaum","year":"1961","unstructured":"B. Gr\u00fcnbaum and T. S. Motzkin. On components in some families of sets,Proceedings of the American Mathematical Society, vol. 12 (1961), pages 607\u2013613.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"BF02574379_CR15","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1111\/j.1749-6632.1979.tb32803.x","volume":"319","author":"A. J. Hoffman","year":"1979","unstructured":"A. J. Hoffman. Binding constraints and Helly numbers,Annals of the New York Academy of Sciences, vol. 319 (1979), pages 284\u2013288.","journal-title":"Annals of the New York Academy of Sciences"},{"key":"BF02574379_CR16","doi-asserted-by":"crossref","unstructured":"G. Kalai. A subexponential randomized simplex algorithm,24th Annual ACM Symposium on the Theory of Computation, 1992, pages 475\u2013482.","DOI":"10.1145\/129712.129759"},{"key":"BF02574379_CR17","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming,Proceedings of the 8th Annual Symposium on Computational Geometry, 1992, pages 1\u20138.","DOI":"10.1145\/142675.142678"},{"key":"BF02574379_CR18","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Linear programming in linear time when the dimension is fixed.SIAM Journal on Computing, vol. 12 (1983), pages 759\u2013776.","journal-title":"SIAM Journal on Computing"},{"key":"BF02574379_CR19","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/BF02187750","volume":"4","author":"N. Megiddo","year":"1989","unstructured":"N. Megiddo. On the ball spanned by balls,Discrete and Computational Geometry, vol. 4 (1989), pages 605\u2013610.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02574379_CR20","unstructured":"N. Megiddo. Personal communication (1991)."},{"key":"BF02574379_CR21","unstructured":"S. Poljak and J. Rohn. Radius of nonsingularity,Mathematics of Systems, Signals and Control (to appear)."},{"key":"BF02574379_CR22","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0024-3795(89)90004-9","volume":"126","author":"J. Rohn","year":"1989","unstructured":"J. Rohn. Linear interval equations,Linear Algebra and Its Applications, vol. 126 (1989), pages 39\u201378.","journal-title":"Linear Algebra and Its Applications"},{"key":"BF02574379_CR23","doi-asserted-by":"crossref","unstructured":"R. Seidel. Linear programming and convex hulls made easy,Proceedings of the 6th Annual Symposium on Computational Geometry, 1990, pages 211\u2013215.","DOI":"10.1145\/98524.98570"},{"key":"BF02574379_CR24","series-title":"Lecture Notes in Computer Science","first-page":"569","volume-title":"Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science","author":"M. Sharir","year":"1992","unstructured":"M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems,Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, 1992, pages 569\u2013579. Lecture Notes in Computer Science, vol. 577 Springer-Verlag, Berlin."},{"key":"BF02574379_CR25","doi-asserted-by":"crossref","unstructured":"S. Toledo. Extremal polygon containment problems,Proceedings of the 7th Annual Symposium on Computational Geometry, 1991, pages 176\u2013185.","DOI":"10.1145\/109648.109668"},{"key":"BF02574379_CR26","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02187722","volume":"4","author":"H. Tverberg","year":"1989","unstructured":"H. Tverberg. Proof of Gr\u00fcnbaum\u2019s conjecture on common transversals for translates,Discrete and Computational Geometry, vol. 4 (1989), pages 191\u2013203.","journal-title":"Discrete and Computational Geometry"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574379.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02574379\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T12:19:23Z","timestamp":1558181963000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02574379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF02574379"],"URL":"http:\/\/dx.doi.org\/10.1007\/bf02574379","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"published":{"date-parts":[[1994,9]]}}}