{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:30:40Z","timestamp":1725474640422},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540499947"},{"type":"electronic","value":"9783540499954"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944836_11","type":"book-chapter","created":{"date-parts":[[2006,11,27]],"date-time":"2006-11-27T23:48:02Z","timestamp":1164671282000},"page":"93-104","source":"Crossref","is-referenced-by-count":0,"title":["Computing a Center-Transversal Line"],"prefix":"10.1007","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Antoni","family":"Sellar\u00e8s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/0221035","volume":"21","author":"P.K. Agarwal","year":"1992","unstructured":"Agarwal, P.K.: Ray shooting and other applications of spanning trees with low stabbing number. SIAM J. Comput.\u00a021, 540\u2013570 (1992)","journal-title":"SIAM J. Comput."},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"P.K. Agarwal","year":"1995","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Dynamic half-space range reporting and its applications. Algorithmica\u00a013, 325\u2013345 (1995)","journal-title":"Algorithmica"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/B978-044482537-7\/50003-6","volume-title":"Handbook of Computational Geometry","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 49\u2013119. Elsevier Science Publishers B.V., North-Holland (2000)"},{"key":"#cr-split#-11_CR4.1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Sharir, M., Welzl, E.: Algorithms for center and Tverberg points. In: Proc. 20th Annu. ACM Sympos. Comput. Geom., pp. 61???67 (2004);","DOI":"10.1145\/997817.997830"},{"key":"#cr-split#-11_CR4.2","unstructured":"Also to appear in ACM Trans. Algorithms"},{"issue":"1","key":"11_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00454-001-0092-1","volume":"28","author":"M. Bern","year":"2002","unstructured":"Bern, M., Eppstein, D.: Multivariate regression depth. Discrete Comput. Geom.\u00a028(1), 1\u201317 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR6","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proc. 15th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. 430\u2013436 (2004)"},{"issue":"2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom.\u00a09(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR8","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"B. Chazelle","year":"2001","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York (2001)"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B. Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M.: Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica\u00a011, 116\u2013132 (1994)","journal-title":"Algorithmica"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Eppstein, D., Miller, G.L., Sturtivant, C., Teng, S.-H.: Approximating center points with iterated Radon points. In: Proc. 9th Annu. ACM Sympos. Comput. Geom., pp. 91\u201398 (1993)","DOI":"10.1145\/160985.161004"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T.K. Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds on planar k-sets and related problems. Discrete Comput. Geom.\u00a019, 373\u2013382 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1007\/BF01236771","volume":"52","author":"V. Dol\u2019nikov","year":"1992","unstructured":"Dol\u2019nikov, V.: A generalization of the sandwich theorem. Mathematical Notes\u00a052, 771\u2013779 (1992)","journal-title":"Mathematical Notes"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02574383","volume":"12","author":"D. Halperin","year":"1994","unstructured":"Halperin, D., Sharir, M.: New bounds for lower envelopes in three dimensions, with applications to visibility in terrains. Discrete Comput. Geom.\u00a012, 313\u2013326 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02574382","volume":"12","author":"S. Jadhav","year":"1994","unstructured":"Jadhav, S., Mukhopadhyay, A.: Computing a centerpoint of a finite planar set of points in linear time. Discrete Comput. Geom.\u00a012, 291\u2013312 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, Berlin (2002)"},{"key":"11_CR16","unstructured":"Naor, N., Sharir, M.: Computing a point in the center of a point set in three dimensions. In: Proc. 2nd Canad. Conf. Comput. Geom., pp. 10\u201313 (1990)"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF02574376","volume":"12","author":"M. Pellegrini","year":"1994","unstructured":"Pellegrini, M.: On lines missing polyhedral sets in 3-space. Discrete Comput. Geom.\u00a012, 203\u2013221 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR18","first-page":"839","volume-title":"Handbook of Discrete and Computational Geometry, ch. 37","author":"M. Pellegrini","year":"2004","unstructured":"Pellegrini, M.: Ray shooting and lines in space. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 37, 2nd edn., pp. 839\u2013856. CRC Press LLC, Boca Raton (2004)","edition":"2"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/PL00009452","volume":"22","author":"P. Rousseeuw","year":"1999","unstructured":"Rousseeuw, P., Hubert, M.: Depth in an arrangement of hyperplanes. Discrete Comput. Geom.\u00a022, 167\u2013176 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"388","DOI":"10.2307\/2670155","volume":"94","author":"P. Rousseeuw","year":"1999","unstructured":"Rousseeuw, P., Hubert, M.: Regression depth. J. Amer. Stat. Assoc.\u00a094, 388\u2013402 (1999)","journal-title":"J. Amer. Stat. Assoc."},{"key":"11_CR21","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.\u00a026, 195\u2013204 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: Proc. 9th Annu. Sympos. Theoretical Aspects of Computer Science, pp. 569\u2013579 (1992)","DOI":"10.1007\/3-540-55210-3_213"},{"issue":"2","key":"11_CR23","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s004540010022","volume":"26","author":"G. Toth","year":"2001","unstructured":"Toth, G.: Point sets with many k-sets. Discrete Comput. Geom.\u00a026(2), 187\u2013194 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1112\/blms\/22.2.183","volume":"22","author":"R.T. \u017divaljevi\u0107","year":"1990","unstructured":"\u017divaljevi\u0107, R.T., Vre\u0107ica, S.T.: An extension of the ham sandwich theorem. Bull. London Math. Soc.\u00a022, 183\u2013186 (1990)","journal-title":"Bull. London Math. Soc."}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944836_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:52:41Z","timestamp":1619495561000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944836_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540499947","9783540499954"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11944836_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}