{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,13]],"date-time":"2025-09-13T16:00:17Z","timestamp":1757779217560},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:p> Efficient detection of multiple inter-related surfaces representing the boundaries of objects of interest in d-D images (d \u2265 3) is important and remains challenging in many medical image analysis applications. In this paper, we study several layered net surface (LNS) problems captured by an interesting type of geometric graphs called ordered multi-column graphs in the d-D discrete space (d \u2265 3 is any constant integer). The LNS problems model the simultaneous detection of multiple mutually related surfaces in three or higher dimensional medical images. Although we prove that the d-D LNS problem (d \u2265 3) on a general ordered multi-column graph is NP-hard, the (special) ordered multi-column graphs that model medical image segmentation have the self-closure structures and thus admit polynomial time exact algorithms for solving the LNS problems. Our techniques also solve the related net surface volume (NSV) problems of computing well-shaped geometric regions of an optimal total volume in a d-D weighted voxel grid. The NSV problems find applications in medical image segmentation and data mining. Our techniques yield the first polynomial time exact algorithms for several high dimensional medical image segmentation problems. Experiments and comparisons based on real medical data showed that our LNS algorithms and software are computationally efficient and produce highly accurate and consistent segmentation results. <\/jats:p>","DOI":"10.1142\/s0218195907002331","type":"journal-article","created":{"date-parts":[[2007,6,21]],"date-time":"2007-06-21T22:42:56Z","timestamp":1182465776000},"page":"261-296","source":"Crossref","is-referenced-by-count":11,"title":["THE LAYERED NET SURFACE PROBLEMS IN DISCRETE GEOMETRY AND MEDICAL IMAGE SEGMENTATION"],"prefix":"10.1142","volume":"17","author":[{"given":"XIAODONG","family":"WU","sequence":"first","affiliation":[{"name":"Dept. of Electrical and Computer Engineering, Dept. of Radiation Oncology, University of Iowa, Iowa City, Iowa 52242, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DANNY Z.","family":"CHEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KANG","family":"LI","sequence":"additional","affiliation":[{"name":"Dept. of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MILAN","family":"SONKA","sequence":"additional","affiliation":[{"name":"Dept. of Electrical and Computer Engineering, University of Iowa, Iowa City, IA 52242-1595, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1109\/42.544503"},{"key":"rf8","unstructured":"R. J.\u00a0Frank, Computers in Cardiology (IEEE, Los Alamitos, 1996)\u00a0pp. 45\u201348."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/383891.383893"},{"key":"rf10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2002.806594"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1002\/net.1012"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1006\/nimg.1999.0534"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014080923068"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.22.11.1268"},{"key":"rf22","volume-title":"Image Processing, Analysis, and Machine Vision","author":"Sonka M.","year":"1999"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1109\/42.370412"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1109\/42.476113"},{"key":"rf25","author":"Spreeuwers L.","journal-title":"Computer Assisted Radiology and Surgery"},{"key":"rf26","first-page":"57","author":"Thedens D. R.","journal-title":"Computers in Cardiology"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1109\/42.370401"},{"key":"rf28","first-page":"303","volume":"10","author":"Woeginger G. J.","journal-title":"Acta Cybernetica"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025829232098"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1109\/42.811276"},{"key":"rf36","first-page":"884","volume":"18","author":"Zhu S.","journal-title":"IEEE Trans. Patt. Anal. Mach. Intell."}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195907002331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:30:11Z","timestamp":1565123411000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195907002331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":20,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,6]]}},"alternative-id":["10.1142\/S0218195907002331"],"URL":"https:\/\/doi.org\/10.1142\/s0218195907002331","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6]]}}}