{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T03:12:49Z","timestamp":1649214769244},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p> Geometric intersection searching problems are a well-studied class of query-retrieval problems with many applications. The goal here is to preprocess a set of geometric objects so that the ones that are intersected by a query object can be reported efficiently. Often, a more general version of the problem arises, where the data comes aggregated in disjoint groups and of interest are the groups, not the individual objects, that are intersected by the query object. One approach to a generalized problem is to ignore the grouping, solve the corresponding classical problem, and then infer the groups from the reported answer. However, this is not efficient, since the number of objects intersected can be much larger than the number of groups (i.e., the output size). The problem of designing efficient, output-sensitive query algorithms for generalized intersection searching has received much attention in recent years, and such solutions have been developed for several problems. <\/jats:p><jats:p> This paper considers a new class of generalized query-retrieval problems. Specifically, given aggregated geometric data the goal is to report the distinct groups such that no objects from those groups are intersected by the query. Of interest in these generalized non-intersection searching problems are solutions where the query time is sensitive to the output size, i.e., the number of groups reported. Unfortunately, the obvious approaches of (i) solving the corresponding generalized intersection searching problem and reporting the complement, or (ii) solving a generalized intersection searching problem with the complement of the query are either inefficient or incorrect. This paper provides efficient, output-sensitive solutions to several generalized non-intersection searching problems, using techniques such as geometric duality, sparsification, persistence, filtering search, and pruning. <\/jats:p>","DOI":"10.1142\/s0218195909003088","type":"journal-article","created":{"date-parts":[[2010,1,7]],"date-time":"2010-01-07T10:22:17Z","timestamp":1262859737000},"page":"479-506","source":"Crossref","is-referenced-by-count":0,"title":["EFFICIENT NON-INTERSECTION QUERIES ON AGGREGATED GEOMETRIC DATA"],"prefix":"10.1142","volume":"19","author":[{"given":"PROSENJIT","family":"GUPTA","sequence":"first","affiliation":[{"name":"International Institute of Information Technology, Gachibowli, Hyderabad 500 032, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RAVI","family":"JANARDAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering, University of Minnesota, Minneapolis, MN 55455, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHIEL","family":"SMID","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187809"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189304"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940884"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.6.541"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/40.1.22"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1137\/0215051"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90151-M"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187835"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1038"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)00019-0"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00183-X"},{"key":"rf19","first-page":"35","volume":"1","author":"Gupta P.","journal-title":"Int. J. Math. Algorith."},{"key":"rf20","unstructured":"P.\u00a0Gupta, R.\u00a0Janardan and M.\u00a0Smid, Handbook of Data Structures, eds. S.\u00a0Sahni and D.\u00a0Mehta (CRC Press, 2004)\u00a0pp. 1\u201317."},{"key":"rf21","doi-asserted-by":"crossref","first-page":"44","DOI":"10.7146\/math.scand.a-12291","volume":"66","author":"Hope K.","journal-title":"Mathem. Scand."},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1142\/S021819599300004X"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2924-7"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69900-9"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"rf29","unstructured":"T. G.\u00a0Szymanski and C. J.\u00a0van Wyk, Layout Analysis and Verification, Physical Design Automation of VLSI Systems, eds. B.\u00a0Preas and M.\u00a0Lorenzetti (Benjamin\/Cummings, 1988)\u00a0pp. 347\u2013407."}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909003088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:24:01Z","timestamp":1565137441000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909003088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":22,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1142\/S0218195909003088"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909003088","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}