{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,18]],"date-time":"2025-04-18T09:44:46Z","timestamp":1744969486763},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,5,7]],"date-time":"2009-05-07T00:00:00Z","timestamp":1241654400000},"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":[[2009,7]]},"DOI":"10.1007\/s00454-009-9178-y","type":"journal-article","created":{"date-parts":[[2009,5,6]],"date-time":"2009-05-06T14:12:25Z","timestamp":1241619145000},"page":"22-36","source":"Crossref","is-referenced-by-count":6,"title":["Constrained Minkowski Sums: A Geometric Framework for Solving Interval Problems in\u00a0Computational Biology Efficiently"],"prefix":"10.1007","volume":"42","author":[{"given":"Thorsten","family":"Bernholt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedrich","family":"Eisenbrand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Hofmeister","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,5,7]]},"reference":[{"issue":"1","key":"9178_CR1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/PL00009337","volume":"19","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Amenta, N., Sharir, M.: Largest placement of one convex polygon inside another. Discrete Comput. Geom. 19(1), 95\u2013104 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"10","key":"9178_CR2","doi-asserted-by":"crossref","first-page":"1294","DOI":"10.1093\/bioinformatics\/btg135","volume":"19","author":"L. Allison","year":"2003","unstructured":"Allison, L.: Longest biased interval and longest non-negative sum interval. Bioinf. Appl. Note 19(10), 1294\u20131295 (2003)","journal-title":"Bioinf. Appl. Note"},{"key":"9178_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. of the 15th Annual ACM Symposium on Theory of Computing (STOC \u201983), pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"9178_CR4","doi-asserted-by":"crossref","unstructured":"Bernholt, T., Hofmeister, T.: An algorithm for a generalized maximum subsequence problem. In: Proc. of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), pp. 178\u2013189 (2006)","DOI":"10.1007\/11682462_20"},{"key":"9178_CR5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S. Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"2","key":"9178_CR6","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0925-7721(93)90001-M","volume":"3","author":"L.P. Chew","year":"1993","unstructured":"Chew, L.P., Kedem, K.: A convex polygon among polygonal obstacles: placement and high-clearance motion. Comput. Geom. 3(2), 59\u201389 (1993)","journal-title":"Comput. Geom."},{"issue":"1","key":"9178_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aos\/996986501","volume":"29","author":"P.L. Davies","year":"2001","unstructured":"Davies, P.L., Kovac, A.: Local extremes, runs, strings and multiresolution (with discussion). Ann. Stat. 29(1), 1\u201365 (2001)","journal-title":"Ann. Stat."},{"key":"9178_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry Algorithms and Applications","author":"M. Berg de","year":"1997","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry Algorithms and Applications. Springer, Berlin (1997)"},{"issue":"1","key":"9178_CR9","first-page":"4","volume":"15","author":"F. Eisenbrand","year":"2008","unstructured":"Eisenbrand, F., Pach, J., Rothvo\u00df, T., Sopher, N.B.: Convexly independent subsets of the Minkowski sum of planar point sets. Electron. J. Comb. 15(1), 4 of Note 8 (2008)","journal-title":"Electron. J. Comb."},{"key":"9178_CR10","doi-asserted-by":"crossref","unstructured":"Fan, T.-H., Lee, S., Lu, H.-I., Tsou, T.-S., Wang, T.C., Yao, A.: An optimal algorithm for maximum-sum segment and its application in bioinformatics. In: Proc. of the 8th International Conference on Implementation and Application of Automata (CIAA 2003), pp. 251\u2013257 (2003)","DOI":"10.1007\/3-540-45089-0_23"},{"issue":"2","key":"9178_CR11","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/j.jcss.2004.08.001","volume":"70","author":"M.H. Goldwasser","year":"2005","unstructured":"Goldwasser, M.H., Kao, M.-Y., Lu, H.-I.: Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. J. Comput. Syst. Sci. 70(2), 128\u2013144 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"9178_CR12","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Ramshaw, L.H., Stolfi, J.: A kinetic framework for computational geometry. In: Proc. of the 24th IEEE Symposium on the Foundations of Computer Science (FOCS \u201983), pp. 100\u2013111 (1983)","DOI":"10.1109\/SFCS.1983.1"},{"issue":"5","key":"9178_CR13","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/BF02187744","volume":"4","author":"L.J. Guibas","year":"1989","unstructured":"Guibas, L.J., Sharir, M., Sifrony, S.: On the general motion-planning problem with two degrees of freedom. Discrete Comput. Geom. 4(5), 491\u2013521 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9178_CR14","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1016\/j.dam.2007.02.005","volume":"155","author":"N. Halman","year":"2007","unstructured":"Halman, N., Onn, S., Rothblum, U.: The convex dimension of a graph. Discrete Appl. Math. 155, 1373\u20131383 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9178_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot Motion Planning","author":"J.C. Latombe","year":"1991","unstructured":"Latombe, J.C.: Robot Motion Planning. Kluwer, Dordrecht (1991)"},{"issue":"3","key":"9178_CR16","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1016\/S0022-0000(02)00010-7","volume":"65","author":"Y.-L. Lin","year":"2002","unstructured":"Lin, Y.-L., Jiang, T., Chao, K.-M.: Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. J. Comput. Syst. Sci. 65(3), 570\u2013586 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9178_CR17","doi-asserted-by":"crossref","unstructured":"Lipson, D., Aumann, Y., Ben-Dor, A., Linial, N., Yakhini, Z.: Efficient calculation of interval scores for DNA copy numbers. In: Proc. of the 9th International Conference on Research in Computational Molecular Biology (RECOMB 2005), pp. 83\u2013100 (2005)","DOI":"10.1007\/11415770_6"},{"key":"9178_CR18","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T. Lozano-Perez","year":"1979","unstructured":"Lozano-Perez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22, 560\u2013570 (1979)","journal-title":"Commun. ACM"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9178-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9178-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9178-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T23:52:10Z","timestamp":1589759530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9178-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,7]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["9178"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9178-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,7]]}}}