{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T06:42:37Z","timestamp":1794379357436,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540200642","type":"print"},{"value":"9783540396581","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39658-1_17","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T19:24:30Z","timestamp":1279826670000},"page":"161-171","source":"Crossref","is-referenced-by-count":10,"title":["Smoothed Motion Complexity"],"prefix":"10.1007","author":[{"given":"Valentina","family":"Damerow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Harald","family":"R\u00e4cke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"17_CR1","unstructured":"Agarwal, P., Har-Peled, S.: Maintaining approximate extent measures of moving points. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 148\u2013157 (2001)"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Banderier, C., Mehlhorn, K., Beier, R.: Smoothed analysis of three combinatorial problems (2002) (manuscript)","DOI":"10.1007\/978-3-540-45138-9_14"},{"key":"17_CR3","unstructured":"Barequet, G., Har-Peled, S.: Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 82\u201391 (1999)"},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1998.0988","volume":"31","author":"J. Basch","year":"1999","unstructured":"Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. Journal of Algorithms\u00a031(1), 1\u201328 (1999)","journal-title":"Journal of Algorithms"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Basch, J., Guibas, L.J., Zhang, L.: Proximity problems on moving points. In: Proceedings of the 13th Annual ACM Symposium on Computational Geometry, pp. 344\u2013351 (1997)","DOI":"10.1145\/262839.262998"},{"key":"17_CR6","unstructured":"Blum, A., Dunagan, J.: Smoothed analysis of the perceptron algorithm. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 905\u2013914 (2002)"},{"issue":"4","key":"17_CR7","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s00454-001-0015-1","volume":"25","author":"L.J. Guibas","year":"2001","unstructured":"Guibas, L.J., Hershberger, J., Suri, S., Zhang, L.: Kinetic connectivity for unit disks. Discrete & Computational Geometry\u00a025(4), 591\u2013610 (2001)","journal-title":"Discrete & Computational Geometry"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Clustering motion. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 84\u201393 (2001)","DOI":"10.1109\/SFCS.2001.959883"},{"key":"17_CR9","unstructured":"Hershberger, J., Suri, S.: Simplified kinetic connectivity for rectangles and hypercubes. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 158\u2013167 (2001)"},{"issue":"1-2","key":"17_CR10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1142\/S0218195902000724","volume":"12","author":"D. Kirkpatrick","year":"2002","unstructured":"Kirkpatrick, D., Snoeyink, J., Speckmann, B.: Kinetic collision detection for simple polygons. International Journal of Computational Geometry and Applications\u00a012(1-2), 3\u201327 (2002)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF00535300","volume":"2","author":"A. R\u00e9nyi","year":"1963","unstructured":"R\u00e9nyi, A., Sulanke, R.: \u00dcber die konvexe H\u00fclle von n zuf\u00e4llig gew\u00e4hlten Punkten. Zentralblatt f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete\u00a02, 75\u201384 (1963)","journal-title":"Zentralblatt f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete"},{"key":"17_CR12","unstructured":"Sankar, A., Spielman, D., Teng, S.: Smoothed analysis of the condition numbers and growth factors of matrices (2002) (manuscript)"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In: Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC), pp. 296\u2013305 (2001)","DOI":"10.1145\/380752.380813"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.: Smoothed analysis of property testing (2002) (manuscript)","DOI":"10.1007\/978-3-540-45078-8_23"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Zhang, L., Devarajan, H., Basch, J., Indyk, P.: Probabilistic analysis for combinatorial functions of moving points. In: Proceedings of the 13th Annual ACM Symposium on Computational Geometry, pp. 442\u2013444 (1997)","DOI":"10.1145\/262839.263075"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39658-1_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T09:00:48Z","timestamp":1559293248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39658-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200642","9783540396581"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39658-1_17","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b13632","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}