{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:23:35Z","timestamp":1725557015149},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135613"},{"type":"electronic","value":"9783642135620"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13562-0_5","type":"book-chapter","created":{"date-parts":[[2010,5,31]],"date-time":"2010-05-31T09:08:30Z","timestamp":1275296910000},"page":"40-49","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Geometric Problems in High Dimension"],"prefix":"10.1007","author":[{"given":"Christian","family":"Knauer","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E. Armaldi","year":"1995","unstructured":"Armaldi, E., Kann, V.: The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science\u00a0147, 181\u2013210 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"5_CR2","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1137\/060669474","volume":"38","author":"B. Aronov","year":"2008","unstructured":"Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput.\u00a038(3), 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci.\u00a054(2), 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR4","unstructured":"Backer, J., Keil, J.: The mono- and bichromatic empty rectangle and square problems in all dimensions. In: Proc. of the 9th Latin American Theoretical Informatics Symposium, Oaxaca, Mexico. LNCS. Springer, Heidelberg (to appear, 2010)"},{"issue":"3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s11222-008-9054-2","volume":"18","author":"D. Bremner","year":"2008","unstructured":"Bremner, D., Chen, D., Iacono, J., Langerman, S., Morin, P.: Output-sensitive algorithms for Tukey depth and related problems. Statistics and Computing\u00a018(3), 259\u2013266 (2008)","journal-title":"Statistics and Computing"},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/11847250_16","volume-title":"Parameterized and Exact Computation","author":"S. Cabello","year":"2006","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C.: On the parameterized complexity of d-dimensional point set pattern matching. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 175\u2013183. Springer, Heidelberg (2006)"},{"key":"5_CR7","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C., Marx, D., Rote, G.: Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. ACM Transactions on Algorithms (2009) (to appear)"},{"key":"5_CR8","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C., Rote, G.: Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. In: Proc. 19th Ann. ACM-SIAM Sympos. Discrete Algorithms, pp. 836\u2013843 (2008)"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: A (slightly) faster algorithm for Klee\u2019s measure problem. In: Proc. 24th Annual Symposium on Computational Geometry, pp. 94\u2013100 (2008)","DOI":"10.1145\/1377676.1377693"},{"issue":"3","key":"5_CR10","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0167-6377(82)90006-2","volume":"1","author":"R. Chandrasekaran","year":"1982","unstructured":"Chandrasekaran, R., Kabadi, S.N., Murthy, K.G.: Some NP-complete problems in linear programming. Operations Research Letters\u00a01(3), 101\u2013104 (1982)","journal-title":"Operations Research Letters"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF02573985","volume":"10","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry\u00a010, 377\u2013409 (1993)","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"5_CR12","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J. Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation\u00a0201(2), 216\u2013231 (2005)","journal-title":"Information and Computation"},{"issue":"8","key":"5_CR13","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J. Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci.\u00a072(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR14","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (November 1999)"},{"issue":"3","key":"5_CR15","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1287\/moor.8.3.381","volume":"8","author":"M.E. Dyer","year":"1983","unstructured":"Dyer, M.E.: The Complexity of Vertex Enumeration Methods. Mathematics of Operations Research\u00a08(3), 381\u2013402 (1983)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"5_CR16","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1023\/A:1020546910706","volume":"23","author":"J. Eckstein","year":"2002","unstructured":"Eckstein, J., Hammer, P.L., Liu, Y., Nediak, M., Simeone, B.: The maximum box problem and its application to data analysis. Comput. Optim. Appl.\u00a023(3), 285\u2013298 (2002)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"5_CR17","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1137\/S0097539797315410","volume":"28","author":"J. Erickson","year":"1999","unstructured":"Erickson, J.: New lower bounds for convex hull problems in odd dimensions. SIAM J. Comput.\u00a028(4), 1198\u20131214 (1999)","journal-title":"SIAM J. Comput."},{"key":"5_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-56686-4_38","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"M.R. Fellows","year":"1993","unstructured":"Fellows, M.R., Koblitz, N.: Fixed-parameter complexity and cryptography. In: Moreno, O., Cohen, G., Mora, T. (eds.) AAECC 1993. LNCS, vol.\u00a0673, pp. 121\u2013131. Springer, Heidelberg (1993)"},{"key":"5_CR19","series-title":"Texts in Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, Heidelberg (2006)"},{"issue":"3","key":"5_CR20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A. Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of O(n2) problems in computational geometry. Comput. Geom. Theory Appl.\u00a05(3), 165\u2013185 (1995)","journal-title":"Comput. Geom. Theory Appl."},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/978-3-642-11269-0_16","volume-title":"IWPEC 2009","author":"P. Giannopoulos","year":"2009","unstructured":"Giannopoulos, P., Knauer, C., Rote, G.: The parameterized complexity of some geometric problems in unbounded dimension. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 198\u2013209. Springer, Heidelberg (2009)"},{"key":"5_CR22","unstructured":"Giannopoulos, P., Knauer, C., Wahlstr\u00f6m, M., Werner, D.: Hardness of discrepancy and related problems parameterized by the dimension. In: 26th European Workshop on Computational Geometry, EuroCG (to appear, 2010)"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jco.2008.10.001","volume":"25","author":"M. Gnewuch","year":"2009","unstructured":"Gnewuch, M., Srivastav, A., Winzen, C.: Finding optimal volume subintervals with k points and calculating the star discrepancy are NP-hard problems. J. Complexity\u00a025, 115\u2013127 (2009)","journal-title":"J. Complexity"},{"issue":"2","key":"5_CR24","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"5_CR25","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00454-004-1108-4","volume":"33","author":"S. Langerman","year":"2005","unstructured":"Langerman, S., Morin, P.: Covering things with things. Discrete & Computational Geometry\u00a033(4), 717\u2013729 (2005)","journal-title":"Discrete & Computational Geometry"},{"issue":"4","key":"5_CR26","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02570713","volume":"14","author":"J. Matousek","year":"1995","unstructured":"Matousek, J.: On geometric optimization with few violated constraints. Discrete & Computational Geometry\u00a014(4), 365\u2013384 (1995)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR27","doi-asserted-by":"publisher","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\u00a031, 114\u2013127 (1984)","journal-title":"J. ACM"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02187916","volume":"3","author":"N. Megiddo","year":"1988","unstructured":"Megiddo, N.: On the complexity of polyhedral separability. Discrete & Computational Geometry\u00a03, 325\u2013337 (1988)","journal-title":"Discrete & Computational Geometry"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0747-7171(08)80067-3","volume":"10","author":"N. Megiddo","year":"1990","unstructured":"Megiddo, N.: On the complexity of some geometric problems in unbounded dimension. J. Symb. Comput.\u00a010, 327\u2013334 (1990)","journal-title":"J. Symb. Comput."},{"key":"5_CR30","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13562-0_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:07Z","timestamp":1606185607000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13562-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135613","9783642135620"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13562-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}