{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T10:50:33Z","timestamp":1790419833241,"version":"4.1.0"},"reference-count":363,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"12","license":[{"start":{"date-parts":[[1984,12,1]],"date-time":"1984-12-01T00:00:00Z","timestamp":470707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Comput."],"published-print":{"date-parts":[[1984,12]]},"DOI":"10.1109\/tc.1984.1676388","type":"journal-article","created":{"date-parts":[[2007,9,4]],"date-time":"2007-09-04T16:35:10Z","timestamp":1188923710000},"page":"1072-1101","source":"Crossref","is-referenced-by-count":177,"title":["Computational Geometry\u2014A Survey"],"prefix":"10.1109","volume":"C-33","author":[{"family":"Lee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref275","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1145\/358656.358681","article-title":"plane-sweeping algorithms for intersecting geometric figures","volume":"25","author":"nievergelt","year":"1982","journal-title":"Commun ACM"},{"key":"ref274","author":"newman","year":"1979","journal-title":"Principles of Interactive Computer Graphics"},{"key":"ref363","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90064-8"},{"key":"ref277","first-page":"75","article-title":"the complexity of computing minimum convex covers for polygons","author":"o'rourke","year":"1982","journal-title":"Proc 20th Allerton Conf Commun Control Comput"},{"key":"ref362","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808755"},{"key":"ref276","article-title":"minimum partitioning of rectilinear regions","author":"ohtsuki","year":"1983","journal-title":"Trans Inform Processing Soc Japan"},{"key":"ref361","doi-asserted-by":"publisher","DOI":"10.1137\/0209028"},{"key":"ref271","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90051-8"},{"key":"ref360","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"},{"key":"ref270","author":"minsky","year":"1966","journal-title":"Perceptron"},{"key":"ref170","author":"graham","year":"1981","journal-title":"Finding the convex hull of a simple polygon"},{"key":"ref273","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934070"},{"key":"ref272","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90124-0"},{"key":"ref172","first-page":"235","article-title":"the decomposition of polygons into convex parts","volume":"1","author":"greene","year":"1983","journal-title":"Advances in Computing Research"},{"key":"ref171","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90013-5"},{"key":"ref174","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90045-5"},{"key":"ref173","author":"gr\ufffdnbaum","year":"1967","journal-title":"Convex Polytopes"},{"key":"ref176","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90010-8"},{"key":"ref175","author":"g\ufffdting","year":"1982","journal-title":"Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles"},{"key":"ref178","author":"hartigan","year":"1975","journal-title":"Clustering Algorithms"},{"key":"ref177","author":"g\ufffdting","year":"1983","journal-title":"Finding rectangle intersections by divide?and-conquer"},{"key":"ref168","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056738"},{"key":"ref169","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675043"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1145\/358315.358392"},{"key":"ref359","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322289"},{"key":"ref31","author":"bentley","year":"1980","journal-title":"Notes on a taxonomy of planar convex hull algorithms"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"ref357","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90021-8"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263991"},{"key":"ref267","author":"megiddo","year":"1981","journal-title":"The maximum coverage location problem"},{"key":"ref358","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.20"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"ref268","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786969"},{"key":"ref355","doi-asserted-by":"publisher","DOI":"10.1137\/0214019"},{"key":"ref35","first-page":"88","article-title":"fast geometric algorithms for vlsi tasks","author":"bentley","year":"1981","journal-title":"Proc Comput Conf"},{"key":"ref269","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90010-7"},{"key":"ref356","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3839"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"ref352","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.167"},{"key":"ref288","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"ref351","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90027-4"},{"key":"ref287","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90077-6"},{"key":"ref354","doi-asserted-by":"publisher","DOI":"10.1137\/0211012"},{"key":"ref286","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241781"},{"key":"ref353","author":"willard","year":"1978","journal-title":"Predicate-oriented database search algorithms"},{"key":"ref285","author":"overmars","year":"1983","journal-title":"The locus approach"},{"key":"ref181","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90044-8"},{"key":"ref284","author":"overmars","year":"1983","journal-title":"Range searching in a set of line segments"},{"key":"ref180","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322124"},{"key":"ref283","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90029-9"},{"key":"ref350","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(80)90073-3"},{"key":"ref282","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90025-0"},{"key":"ref281","author":"ottmann","year":"1982","journal-title":"Dynamic sets of points"},{"key":"ref185","author":"imai","year":"1984","journal-title":"Dynamic orthogonal segment intersection search"},{"key":"ref280","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"},{"key":"ref184","author":"imai","year":"1983","journal-title":"Efficient algorithms for geometric graph search problems"},{"key":"ref183","article-title":"an efficient algorithm for finding a maximum matching of an intersection graph of horizontal and vertical line segments","author":"imai","year":"0","journal-title":"Papers IECE Tech Group Circuits and Systems"},{"key":"ref182","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90012-3"},{"key":"ref189","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90006-3"},{"key":"ref188","doi-asserted-by":"publisher","DOI":"10.1007\/BF02218436"},{"key":"ref187","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90020-3"},{"key":"ref186","doi-asserted-by":"publisher","DOI":"10.1137\/0214006"},{"key":"ref28","year":"0"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"ref179","article-title":"space sweep solves intersection of two convex polyhedra elegantly","author":"hertel","year":"0","journal-title":"Acta Informatica"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"ref348","author":"van leeuwen","year":"1980","journal-title":"Dynamic systems of static data structures"},{"key":"ref20","first-page":"159","article-title":"algorithms for computing the d-dimensional voronoi diagrams and their duals","volume":"1","author":"avis","year":"1983","journal-title":"Advances in Computing Research"},{"key":"ref349","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-10856-4_78","volume":"118","author":"van leeuwen","year":"1981","journal-title":"Mathematical Foundations of Computer Science Lecture Notes in Computer Science"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675729"},{"key":"ref21","author":"avis","year":"0","journal-title":"Computational Geometry"},{"key":"ref344","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675881"},{"key":"ref24","first-page":"179","article-title":"fast algorithms for lsi artwork analysis","volume":"2","author":"baird","year":"1978","journal-title":"J Design Automat Fault-Tolerant Computing"},{"key":"ref345","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(80)90034-9"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(81)90002-9"},{"key":"ref346","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90016-5"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808735"},{"key":"ref278","author":"o'rourke","year":"1984","journal-title":"An optimal algorithm for finding minimal enclosing triangles"},{"key":"ref347","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90064-2"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.2307\/2005017"},{"key":"ref279","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(82)90023-5"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241747"},{"key":"ref293","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-93208-3"},{"key":"ref51","first-page":"658","article-title":"triangullation of 3d objects","author":"boissonnat","year":"1981","journal-title":"Proc 7th tnt Joint Conf Artificial Intell"},{"key":"ref292","doi-asserted-by":"publisher","DOI":"10.1137\/0210040"},{"key":"ref295","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808672"},{"key":"ref294","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.7"},{"key":"ref297","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/3-540-08353-7_166","article-title":"the medial axis of a simple polygon","author":"preparata","year":"1977","journal-title":"Proc 6th Symp Math Found Comput Sci Lecture Notes in Computer Science 53"},{"key":"ref296","doi-asserted-by":"publisher","DOI":"10.1145\/355759.355761"},{"key":"ref299","doi-asserted-by":"publisher","DOI":"10.1137\/0210035"},{"key":"ref298","doi-asserted-by":"publisher","DOI":"10.1145\/359131.359132"},{"key":"ref154","doi-asserted-by":"publisher","DOI":"10.1145\/356625.356627"},{"key":"ref153","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322281"},{"key":"ref156","doi-asserted-by":"publisher","DOI":"10.1145\/360881.360919"},{"key":"ref155","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1967.264724"},{"key":"ref150","author":"francis","year":"1974","journal-title":"Facility Layout and Location"},{"key":"ref152","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359553"},{"key":"ref291","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"ref151","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90035-4"},{"key":"ref290","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90093-4"},{"key":"ref146","doi-asserted-by":"publisher","DOI":"10.1007\/BF02263430"},{"key":"ref147","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1109\/T-C.1975.224276","article-title":"decomposition of polygons into simpler components: feature generation for syntactic pattern recognition","volume":"c 24","author":"feng","year":"1975","journal-title":"IEEE Transactions on Computers"},{"key":"ref148","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-079050-0.50007-2"},{"key":"ref149","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90085-1"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.1979.tb00695.x"},{"key":"ref289","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/BFb0017314","author":"overmars","year":"1981","journal-title":"Lecture Notes in Computer Science 104"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1145\/965103.807434"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1145\/359046.359048"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802202"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.162"},{"key":"ref54","first-page":"35","author":"borodin","year":"1973","journal-title":"Currents in the Theory of Computing"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.2307\/142716"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1137\/0210056"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803652"},{"key":"ref167","author":"gonzalez","year":"1975","journal-title":"Algorithms on sets and related problems"},{"key":"ref166","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(83)90111-1"},{"key":"ref165","author":"gilbert","year":"1979","journal-title":"New results on planar triangulations"},{"key":"ref164","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"ref163","author":"garey","year":"1979","journal-title":"Computers and Intractability A Guide to the Theory of NP-Completeness"},{"key":"ref162","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803626"},{"key":"ref161","doi-asserted-by":"publisher","DOI":"10.1145\/362912.362921"},{"key":"ref160","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90003-0"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90156-X"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90041-8"},{"key":"ref5","first-page":"483","article-title":"efficient convex hull algorithms for pattern recognition applications","author":"akl","year":"1978","journal-title":"Proc 4th Int Joint Conf Pattern Recognition"},{"key":"ref159","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224110"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1147\/rd.206.0590"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90072-3"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90040-8"},{"key":"ref157","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1972.24"},{"key":"ref158","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.34"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675628"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/355921.355927"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056845"},{"key":"ref47","author":"bezier","year":"1972","journal-title":"Numerical Control?Mathematics and Applications"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90051-0"},{"key":"ref41","first-page":"193","article-title":"a problem in multivariate statistics: algorithms, data structure and applications","author":"bentley","year":"1977","journal-title":"Proc 15th Allerton Conf Commun Contr Comput"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90070-9"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90034-4"},{"key":"ref320","author":"seidel","year":"1984","journal-title":"A method for lower bounds for certain geometric problems"},{"key":"ref321","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803772"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90028-5"},{"key":"ref72","first-page":"1","article-title":"the polygon containment problem","volume":"1","author":"chazelle","year":"1983","journal-title":"Advances of Computing Research"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.58"},{"key":"ref70","year":"1980"},{"key":"ref76","first-page":"427","article-title":"optimal algorithms for computing depths and layers","author":"chazelle","year":"1983","journal-title":"Proc 21st Allerton Conf Commun Control Comput"},{"key":"ref318","first-page":"94","article-title":"the complexity of voronoi diagrams in higher dimensions","author":"seidel","year":"1982","journal-title":"Proc 20th Allerton Conf Commun Control and Comput"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808674"},{"key":"ref317","author":"seidel","year":"1981","journal-title":"A convex hull algorithm optimal for points in even dimensions"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90123-0"},{"key":"ref316","author":"schwartz","year":"1982","journal-title":"On the piano movers problem"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.17"},{"key":"ref315","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90051-X"},{"key":"ref314","author":"schoone","year":"1980","journal-title":"Triangulating a star-shaped polygon"},{"key":"ref313","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80029-3"},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12689-9_93"},{"key":"ref312","article-title":"a visibility problem in vlsi layout compaction","volume":"2","author":"schlag","year":"0","journal-title":"Advances in Computing Research"},{"key":"ref79","author":"chazelle","year":"1984","journal-title":"Fast searching in a real algebraic manifold with applications to geometric complexity"},{"key":"ref311","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.47"},{"key":"ref319","year":"1982"},{"key":"ref310","first-page":"21","article-title":"a linear time algorithm for decomposing rectilinear star-shaped polygons into convex quadrilaterals","author":"sack","year":"1981","journal-title":"Proc 19th Allerton Conf Commun Control Comput"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(78)90110-9"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90074-7"},{"key":"ref61","author":"brown","year":"1979","journal-title":"Geometric transformations for fast geometric algorithms"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.6312179"},{"key":"ref305","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321730"},{"key":"ref64","first-page":"230","article-title":"some approaches to best match file searching","volume":"16","author":"burkhard","year":"1973","journal-title":"Commun Ass Comput Mach"},{"key":"ref304","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90027-8"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1137\/0211006"},{"key":"ref307","author":"roger","year":"1964","journal-title":"Packing and Covering"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90021-2"},{"key":"ref306","author":"riesenfeld","year":"1973","journal-title":"Applications of B-Spline Approximation to Geometric Problems of Computer-Aided Design"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620080402"},{"key":"ref301","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90055-0"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1145\/321556.321564"},{"key":"ref300","doi-asserted-by":"publisher","DOI":"10.1145\/359423.359430"},{"key":"ref69","author":"chazelle","year":"0","journal-title":"Computational geometry and convexity"},{"key":"ref303","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(72)80034-5"},{"key":"ref302","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2004.12"},{"key":"ref309","first-page":"64","article-title":"an o (n log n) algorithm for decomposing simple rectlinear polygons into convex quadrilaterals","author":"sack","year":"1982","journal-title":"Proc 20th Allerton onf Commun Control Comput"},{"key":"ref308","author":"rosenfeld","year":"1969","journal-title":"Picture Processing by Computers"},{"key":"ref197","author":"keil","year":"0","journal-title":"Computational Geometry"},{"key":"ref198","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"ref199","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.15"},{"key":"ref193","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"ref194","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"ref195","doi-asserted-by":"publisher","DOI":"10.1007\/BF01937321"},{"key":"ref196","author":"keil","year":"1983","journal-title":"Decomposing polygons into simpler components"},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715923"},{"key":"ref94","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.16"},{"key":"ref190","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(83)90065-1"},{"key":"ref93","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90073-5"},{"key":"ref191","doi-asserted-by":"publisher","DOI":"10.1137\/0604020"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676186"},{"key":"ref192","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.235263"},{"key":"ref342","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(85)90038-8"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"key":"ref343","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(82)90057-7"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238188"},{"key":"ref340","doi-asserted-by":"publisher","DOI":"10.1007\/BF02243778"},{"key":"ref341","doi-asserted-by":"publisher","DOI":"10.1007\/BF01008046"},{"key":"ref336","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90010-6"},{"key":"ref335","doi-asserted-by":"publisher","DOI":"10.1145\/356625.356626"},{"key":"ref334","first-page":"215","article-title":"grid heuristics for some geometricv covering problems","volume":"1","author":"supowit","year":"1983","journal-title":"Advances in Computing Research"},{"key":"ref333","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90002-5"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1007\/BF02237955"},{"key":"ref339","article-title":"solving geometric problems with the rotating calipers","author":"toussaint","year":"1983","journal-title":"Proc IEEE MELECON '83"},{"key":"ref99","author":"dewdney","year":"1977","journal-title":"Complexity of nearest neighbor searching in three and higher dimensions"},{"key":"ref338","author":"toussaint","year":"1981","journal-title":"Pattern Recognition Theory and Applications"},{"key":"ref96","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.22"},{"key":"ref337","first-page":"1324","article-title":"pattern recognition and geometrical complexity","author":"toussaint","year":"1980","journal-title":"Proc 5th Int Conf Pattern Recog"},{"key":"ref97","author":"dantzig","year":"1963","journal-title":"Linear Programming and Extensions"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804396"},{"key":"ref81","author":"chazelle","year":"0","journal-title":"New upper bounds for neighbor searching"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12920-0_4"},{"key":"ref83","first-page":"146","article-title":"detection is easier than computation","author":"chazelle","year":"1980","journal-title":"Proc 12th ACM Annu Symp Theory Comput"},{"key":"ref330","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1980.4767016"},{"key":"ref331","first-page":"309","volume":"pami 4","year":"1982","journal-title":"IEEE Trans Pattern Recog Mach Intell"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1137\/0213031"},{"key":"ref332","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90027-0"},{"key":"ref89","first-page":"447","article-title":"triangulating a polygon by divide-and-conquer","author":"chazelle","year":"1983","journal-title":"Proc 21st Allerton Conf Commun Control Comput"},{"key":"ref323","author":"shamos","year":"1978","journal-title":"Computational Geometry"},{"key":"ref322","first-page":"251","author":"shamos","year":"1976","journal-title":"Algorithms and Complexity"},{"key":"ref325","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.16"},{"key":"ref324","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.8"},{"key":"ref327","doi-asserted-by":"publisher","DOI":"10.1137\/0901028"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0015733"},{"key":"ref326","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808676"},{"key":"ref86","author":"chazelle","year":"1984","journal-title":"Fractional cascading A data structuring technique with geometric applications"},{"key":"ref329","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675973"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.75"},{"key":"ref328","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/BF01933636","article-title":"the rectangle intersection problem revisited","volume":"20","author":"six","year":"1980","journal-title":"BIT"},{"key":"ref88","author":"chazelle","year":"1983","journal-title":"Unraveling the segment tree"},{"key":"ref200","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"ref101","first-page":"181","article-title":"finding smallest polygons","volume":"1","author":"dobkin","year":"1983","journal-title":"Advances in Computing Research"},{"key":"ref100","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80051-7"},{"key":"ref209","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/net.3230110307","article-title":"finding minimum rectilinear distance paths in the presence of barriers","volume":"11","author":"larson","year":"1981","journal-title":"Networks"},{"key":"ref203","doi-asserted-by":"publisher","DOI":"10.1007\/BF01224932"},{"key":"ref204","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90005-7"},{"key":"ref201","doi-asserted-by":"publisher","DOI":"10.1137\/0215021"},{"key":"ref202","author":"kirkpatrick","year":"1983","journal-title":"The ultimate planar convex hull algorithm?"},{"key":"ref207","doi-asserted-by":"publisher","DOI":"10.1145\/1008328.1008329"},{"key":"ref208","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"ref205","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70044-X"},{"key":"ref206","volume":"3","author":"knuth","year":"1973","journal-title":"The Art of Computer Programming Sorting and Searching"},{"key":"ref211","author":"lawson","year":"1976","journal-title":"C1-compatible interpolation over a triangle"},{"key":"ref210","first-page":"241","article-title":"4-dimensional binary search trees as a means to speed up associative searches in design rule verification of integrated circuits","volume":"2","author":"lauther","year":"1978","journal-title":"J Design Automat Fault-Tolerant Computing"},{"key":"ref212","author":"lawson","year":"1976","journal-title":"Integrals of a C1-compatible triangular surface element"},{"key":"ref213","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-587260-7.50011-X"},{"key":"ref214","author":"lee","year":"1978","journal-title":"Proximity and reachability in the plane"},{"key":"ref215","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322219"},{"key":"ref216","author":"lee","year":"1980","journal-title":"Farthest neighbor Voronoi diagrams and applications"},{"key":"ref217","author":"lee","year":"1980","journal-title":"On finding the convex hull of a simple polygon"},{"key":"ref218","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993195"},{"key":"ref219","doi-asserted-by":"publisher","DOI":"10.1145\/965161.806787"},{"key":"ref220","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676031"},{"key":"ref222","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(83)90065-8"},{"key":"ref221","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1982.4767267"},{"key":"ref229","doi-asserted-by":"publisher","DOI":"10.1137\/0206043"},{"key":"ref228","author":"lee","year":"1983","journal-title":"Routing around circles"},{"key":"ref227","author":"lee","year":"1984","journal-title":"Computing visibility polygon from an edge"},{"key":"ref226","doi-asserted-by":"publisher","DOI":"10.1137\/0210006"},{"key":"ref225","author":"lee","year":"0","journal-title":"Computational Geometry"},{"key":"ref224","doi-asserted-by":"publisher","DOI":"10.1007\/BF00989481"},{"key":"ref223","first-page":"91-","article-title":"maximum clique problem of rectangle graphs","volume":"1","author":"lee","year":"1983","journal-title":"Advances in Computing Research"},{"key":"ref127","author":"edelsbrunner","year":"1982","journal-title":"Intersection problems in computational geometry"},{"key":"ref126","first-page":"34","article-title":"a note on dynamic range searching","volume":"15","author":"edelsbrunner","year":"1981","journal-title":"Bull EATCS"},{"key":"ref125","author":"edelsbrunner","year":"1980","journal-title":"Dynamic data structures for orthogonal intersection queries"},{"key":"ref124","doi-asserted-by":"publisher","DOI":"10.1080\/00207168308803365"},{"key":"ref129","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"ref128","author":"edelsbrunner","year":"1982","journal-title":"On computing the extreme distances between two convex polygons"},{"key":"ref130","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90053-3"},{"key":"ref133","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934440"},{"key":"ref134","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.11"},{"key":"ref131","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90103-1"},{"key":"ref132","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90090-4"},{"key":"ref232","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90021-9"},{"key":"ref233","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"ref230","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90066-2"},{"key":"ref231","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322142"},{"key":"ref239","article-title":"efficient algorithms for euclidean 1-line center and problems","author":"lee","year":"1984","journal-title":"Proc ISOLDE III"},{"key":"ref238","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90033-X"},{"key":"ref235","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263763"},{"key":"ref234","doi-asserted-by":"publisher","DOI":"10.1007\/BF00977785"},{"key":"ref237","doi-asserted-by":"publisher","DOI":"10.1145\/320613.320618"},{"key":"ref236","doi-asserted-by":"publisher","DOI":"10.1137\/0209017"},{"key":"ref136","author":"edelsbrunner","year":"1981","journal-title":"Connected components of orthogonal geometric objects"},{"key":"ref135","year":"1983"},{"key":"ref138","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90030-6"},{"key":"ref137","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90068-0"},{"key":"ref139","author":"edelsbrunner","year":"1983","journal-title":"Some methods of computational geometry applied to computer graphics"},{"key":"ref140","first-page":"35","article-title":"graphics in flatland: a case study","volume":"1","author":"edelsbrunner","year":"1983","journal-title":"Advances in Computing Research"},{"key":"ref141","author":"edelsbrunner","year":"1983","journal-title":"Multidimensional data structures and algorithms A bibiliography"},{"key":"ref142","author":"edelsbrunner","year":"1982","journal-title":"Halfplanar range estimation"},{"key":"ref143","author":"edelsbrunner","year":"1983","journal-title":"Halfplanar range search in linear space and O(n0 695) query time"},{"key":"ref144","author":"gindy","year":"1984","journal-title":"An efficient algorithm for computing the weak visibility polygon from an edge in simple polygons"},{"key":"ref2","first-page":"44","article-title":"interference detection and collision avoidance among three-dimensional objects","author":"ahuja","year":"1980","journal-title":"Proc 1st Annu Nat Conf Artificial Intell"},{"key":"ref145","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90019-5"},{"key":"ref1","author":"aho","year":"1974","journal-title":"The Design and Analysis of Computer Algorithms"},{"key":"ref241","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130308"},{"key":"ref242","doi-asserted-by":"crossref","first-page":"245","DOI":"10.3233\/FI-1978-2116","article-title":"on two dimensional data organization ii","volume":"2","author":"lipski","year":"1979","journal-title":"Fundamenta Informaticae"},{"key":"ref243","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90023-7"},{"key":"ref244","first-page":"235","volume":"1","author":"lipski","year":"1980","journal-title":"Finding the contour of a union of iso-oriented rectangles"},{"key":"ref240","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012784"},{"key":"ref248","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"ref247","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.6"},{"key":"ref246","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90008-0"},{"key":"ref245","first-page":"301","volume":"3","year":"1980","journal-title":"J Algorith"},{"key":"ref249","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"ref109","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90054-0"},{"key":"ref108","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90026-0"},{"key":"ref107","doi-asserted-by":"publisher","DOI":"10.1137\/0205015"},{"key":"ref106","author":"dobkin","year":"0","journal-title":"Fast algorithms for preprocessed polyhedral intersection detection"},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90007-0"},{"key":"ref104","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90120-7"},{"key":"ref103","author":"dobkin","year":"0","journal-title":"Space searching for intersecting objects"},{"key":"ref102","author":"dobkin","year":"1984","journal-title":"Organizing points in two and three dimensions"},{"key":"ref111","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.18"},{"key":"ref112","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322264"},{"key":"ref110","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90152-2"},{"key":"ref250","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90119-3"},{"key":"ref251","author":"manber","year":"1982","journal-title":"Probabilistic nondeterministic and alternating decision trees"},{"key":"ref254","first-page":"17","author":"maurer","year":"1979","journal-title":"Discrete Structures and Algorithms"},{"key":"ref255","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90069-3"},{"key":"ref252","author":"mairson","year":"1984","journal-title":"Reporting and counting line segment intersections"},{"key":"ref253","year":"0"},{"key":"ref257","author":"mccreight","year":"1981","journal-title":"Priority search trees"},{"key":"ref256","author":"mccreight","year":"1980","journal-title":"Efficient algorithms for enumerating intersecting intervals and rectangles"},{"key":"ref10","author":"asano","year":"1984","journal-title":"Partitioning a polygonal region into trapezoids"},{"key":"ref259","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/19.2.178"},{"key":"ref11","first-page":"31","article-title":"partitioning polygonal regions into triangles","author":"asano","year":"1983","journal-title":"Papers of Tech Groups of IECE"},{"key":"ref258","author":"mckenna","year":"1983","journal-title":"Finding the minimum vertex distance between two disjoint convex polygons in linear time"},{"key":"ref12","author":"asano","year":"1984","journal-title":"Polygon triangulation Efficiency and minimality"},{"key":"ref13","author":"asano","year":"0","journal-title":"Computational Geometry"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90042-X"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.13"},{"key":"ref16","author":"aurenhammer","year":"1983","journal-title":"Power diagrams Properties algorithms and applications"},{"key":"ref118","author":"dyer","year":"1980","journal-title":"A simplified O(n log n) algorithm for the intersection of 3-polyhedra"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(84)90064-5"},{"key":"ref117","first-page":"389","article-title":"query performance of a many-dimensional bestmatch algorithm","author":"dunlavey","year":"1981","journal-title":"Proc 19th Allerton Conf Commun Control Comput"},{"key":"ref18","first-page":"35","article-title":"lower bounds for geometric problems","author":"avis","year":"1980","journal-title":"Proc 18th Allerton Conf Commun Contr Comput"},{"key":"ref19","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1002\/net.3230130404","article-title":"a survey of heuristics for the weighted matching problem","volume":"13","author":"avis","year":"1983","journal-title":"Networks"},{"key":"ref119","doi-asserted-by":"publisher","DOI":"10.1137\/0213003"},{"key":"ref114","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.28"},{"key":"ref113","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90031-6"},{"key":"ref116","author":"duda","year":"1973","journal-title":"Pattern Classification and Scene Analysis"},{"key":"ref115","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.7.848"},{"key":"ref120","author":"edahiro","year":"1983","journal-title":"A new point-location algorithm and its practical efficiency?Comparison with existing algorithms"},{"key":"ref121","doi-asserted-by":"publisher","DOI":"10.1145\/355759.355766"},{"key":"ref122","author":"edelsbrunner","year":"1979","journal-title":"Optimizing the dynamization of decomposable searching problems"},{"key":"ref123","doi-asserted-by":"publisher","DOI":"10.1080\/00207168308803365"},{"key":"ref260","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(85)90039-X"},{"key":"ref261","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90027-1"},{"key":"ref262","author":"megiddo","year":"1981","journal-title":"On some planar location problems"},{"key":"ref263","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"ref264","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"key":"ref265","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"ref266","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"}],"container-title":["IEEE Transactions on Computers"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/12\/35234\/01676388.pdf?arnumber=1676388","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T15:40:08Z","timestamp":1638200408000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1676388\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,12]]},"references-count":363,"journal-issue":{"issue":"12"},"URL":"https:\/\/doi.org\/10.1109\/tc.1984.1676388","relation":{},"ISSN":["0018-9340"],"issn-type":[{"value":"0018-9340","type":"print"}],"subject":[],"published":{"date-parts":[[1984,12]]}}}