{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T06:06:01Z","timestamp":1648620361087},"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":[[2011,6]]},"abstract":"<jats:p> Let P,Q \u2286 \u211d<jats:sup>2<\/jats:sup> be two n-point multisets and Ar \u2265 b be a set of \u03bb inequalities on x and y, where A \u2208 \u211d<jats:sup>\u03bb\u00d72<\/jats:sup>, [Formula: see text], and b \u2208 \u211d<jats:sup>\u03bb<\/jats:sup>. Define the constrained Minkowski sum(P \u2295 Q)<jats:sub>Ar\u2265 b <\/jats:sub> as the multiset {(p + q)|p \u2208 P, q \u2208 Q,A(p + q) \u2265 b }. Given P, Q, Ar \u2265 b , an objective function f : \u211d<jats:sup>2<\/jats:sup> \u2192 \u211d, and a positive integer k, the MINKOWSKI SUM SELECTION problem is to find the kth largest objective value among all objective values of points in (P \u2295 Q)<jats:sub>Ar\u2265 b <\/jats:sub>. Given P, Q, Ar \u2265 b , an objective function f : \u211d<jats:sup>2<\/jats:sup> \u2192 \u211d, and a real number \u03b4, the MINKOWSKI SUM FINDING problem is to find a point (x*, y*) in (P \u2295 Q)<jats:sub>Ar\u2265 b <\/jats:sub> such that |f(x*,y*) - \u03b4| is minimized. For the MINKOWSKI SUM SELECTION problem with linear objective functions, we obtain the following results: (1) optimal O(n log n)-time algorithms for \u03bb = 1; (2) O(n log <jats:sup>2<\/jats:sup> n)-time deterministic algorithms and expected O(n log n)-time randomized algorithms for any fixed \u03bb &gt; 1. For the MINKOWSKI SUM FINDING problem with linear objective functions or objective functions of the form [Formula: see text], we construct optimal O(n log n)-time algorithms for any fixed \u03bb \u2265 1. As a byproduct, we obtain improved algorithms for the LENGTH-CONSTRAINED SUM SELECTION problem and the DENSITY FINDING problem. <\/jats:p>","DOI":"10.1142\/s0218195911003664","type":"journal-article","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T15:33:53Z","timestamp":1309275233000},"page":"283-311","source":"Crossref","is-referenced-by-count":0,"title":["MINKOWSKI SUM SELECTION AND FINDING"],"prefix":"10.1142","volume":"21","author":[{"given":"CHENG-WEI","family":"LUO","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 106, Taiwan"}]},{"given":"HSIAO-FEI","family":"LIU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 106, Taiwan"}]},{"given":"PENG-AN","family":"CHEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 106, Taiwan"}]},{"given":"KUN-MAO","family":"CHAO","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, Graduate Institute of Biomedical Electronics and Bioinformatics, Graduate Institute of Networking and Multimedia, National Taiwan University, Taipei, Taiwan 106, Taiwan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg135"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0076-x"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.08.006"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/0218055"},{"key":"rf8","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000020"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/0213002"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.001"},{"key":"rf12","first-page":"219","volume":"10","author":"Huang X.","journal-title":"Comput. Appl. Biosci."},{"key":"rf13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1038\/79189","volume":"26","author":"Ioshikhes I.","journal-title":"Nature Genetics"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9023-8"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.027"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00010-7"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/19.1.151"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.215"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90177-J"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009190"},{"key":"rf22","first-page":"199","author":"Ohler U.","journal-title":"Bioinformatics"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/19.2.297"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195911003664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:23:53Z","timestamp":1565137433000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195911003664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":20,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.1142\/S0218195911003664"],"URL":"https:\/\/doi.org\/10.1142\/s0218195911003664","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6]]}}}