{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T06:01:53Z","timestamp":1715061713286},"reference-count":35,"publisher":"World Scientific Pub Co Pte Lt","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> The 3-D static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to deliver a prescribed radiation dose to a target tumor accurately and efficiently. The treatment time and machine delivery error are two crucial factors to the solution (i.e., a treatment plan) for the SLS problem. In this paper, we prove that the 3-D SLS problem is NP-hard, and present the first ever algorithm for the 3-D SLS problem that can determine a tradeoff between the treatment time and machine delivery error (also called the \"tongue-and-groove\" error in medical literature). Our new 3-D SLS algorithm with error control gives the users (e.g., physicians) the option of specifying a machine delivery error bound, and subject to the given error bound, the algorithm computes a treatment plan with the minimum treatment time. We formulate the SLS problem with error control as computing a k-weight shortest path in a directed graph and build the graph by computing g-matchings and minimum cost flows. Further, we extend our 3-D SLS algorithm to all the popular radiotherapy machine models with different constraints. In our extensions, we model the SLS problems for some of the radiotherapy systems as computing a minimum g-path cover of a directed acyclic graph. We implemented our new 3-D SLS algorithm suite and conducted an extensive comparison study with commercial planning systems and well-known algorithms in medical literature. Some of our experimental results based on real medical data are presented. <\/jats:p>","DOI":"10.1142\/s0218195906001999","type":"journal-article","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T12:53:13Z","timestamp":1146142393000},"page":"175-204","source":"Crossref","is-referenced-by-count":11,"title":["GENERALIZED GEOMETRIC APPROACHES FOR LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY"],"prefix":"10.1142","volume":"16","author":[{"given":"DANNY Z.","family":"CHEN","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA"}]},{"given":"XIAOBO X.","family":"HU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA"}]},{"given":"SHUANG","family":"LUAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA"}]},{"given":"SHAHID A.","family":"NAQVI","sequence":"additional","affiliation":[{"name":"Department of Radiation Oncology, University of Maryland School of Medicine, Baltimore, MD 21201-1595, USA"}]},{"given":"CHAO","family":"WANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA"}]},{"given":"CEDRIC X.","family":"YU","sequence":"additional","affiliation":[{"name":"Department of Radiation Oncology, University of Maryland School of Medicine, Baltimore, MD 21201-1595, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993"},{"key":"rf3","author":"Baatar D.","journal-title":"Discrete Applied Mathematics"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/322003.322005"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0360-3016(94)90366-2"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0360-3016(94)90200-3"},{"key":"rf10","first-page":"1007","volume":"21","author":"Boyer A. L.","journal-title":"Med. Phys."},{"key":"rf12","volume":"9","author":"Boyer A. L&gt;","journal-title":"Seminar in Radiat. Oncol."},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195904001494"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1169-7"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/43\/9\/007"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1118\/1.1406518"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/46\/4\/310"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/0360-3016(92)90959-L"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1118\/1.598081"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0360-3016(90)90673-8"},{"key":"rf23","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/39\/2\/002"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/0360-3016(89)90973-5"},{"key":"rf27","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E.","year":"1976"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/0360-3016(91)90283-A"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1118\/1.596533"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/48\/15\/306"},{"key":"rf32","first-page":"1404","volume":"30","author":"Luan S.","journal-title":"Med. Phys."},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1118\/1.1646471"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/48\/14\/305"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1016\/0360-3016(93)90316-N"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1016\/S0360-3016(98)00430-1"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/41\/10\/017"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1887\/0750302542"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1887\/0750303972"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/43\/2\/003"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1118\/1.598315"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/40\/9\/004"},{"key":"rf44","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/43\/5\/022"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1088\/0031-9155\/40\/2\/008"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906001999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:20:32Z","timestamp":1565191232000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906001999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":35,"journal-issue":{"issue":"02n03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0218195906001999"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906001999","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}