-- -- ComputationalGeometryBibliography 1 1 A. Abdullah. Bottleneck identification in general tional Geometry: Papers from the DIMACS Special Year. junctions. InProc.3rdCanad.Conf.Comput.Geom.(1991), [2567,A-GPA-DU-91] 26-28. [2686,A-BIGJ-3CCCG-91] 15 P. K. Agarwal. Intersection and decomposition algo- S.Abhyankar. Seealso275[723]. rithmsforplanararrangements,CambridgeUniversityPress, New York, NY (1991). Keywords: arrangement, partition, 2 S. S. Abhyankar and C. Bajaj. Automatic rational Davenport-Schinzelsequences. [2566,A-IDAPA-CUP-91] parameterization of curves and surfaces I: conics and con- icoids. Comput.-Aided Design 19 (1987), 11-14. Keywords: 16 P. K. Agarwal. Partitioningarrangementsof lines: I. algebraic geometry, design of algorithms, computer graphics, Anefficientdeterministicalgorithm. DiscreteComput.Geom. CAD. [1019,AB-ARPCSICC-CAD-87] 5(1990),449-483. Keywords: deterministicpartitioning,ran- dom sampling, arrangements of lines. [2359, A-PALIEDA- 3 S.S.AbhyankarandS.Chandrasekar. Improperinter- DCG-90] section of algebraic curves. In Proc. 1st Canad. Conf. Com- put.Geom.(1989),10. [2641,AC-IIAC-1CCCG-89] 17 P.K.Agarwal. Partitioningarrangementsoflines: II. Applications. Discrete Comput. Geom. 5 (1990), 533-573. 4 S. S. Abhyankar, S. Chandrasekar and V. Chandru. Keywords: random sampling, arrangements, divide-and- Degree complexity bounds on the intersection of algebraic conquer. [2360,A-PALIA-DCG-90] curves. In Proc. 5th Annu. ACM Sympos. Comput. Geom. (1989),88-93. [2136,ACC-DCBIAC-5SCG-89] 18 P.K.Agarwal. Rayshootingandotherapplicationsof spanning trees and low stabbing number. In Proc. 5th Annu. 5 S. S. Abhyankar, S. Chandrasekar and V. Chandru. ACM Sympos. Comput. Geom. (1989), 315-325. [2161, A- Intersectionof algebraicspace curves. TechnicalReportCC- RSOASTLSN-5SCG-89] 88-13,Dept.Math.,PurdueUniv.,WestLafayette,IN(1988). [1885,ACC-IASC-PU-88] 19 P.K.Agarwal,A.Aggarwal,B.Aronov,S.Kosaraju, B. Schieber and S. Suri. Computing external farthest neigh- C.T.Abraham. Seealso1171[246]. bors. Discrete Appl. Math. ?? (1991), ??-??. Keywords: 6 S. Abramovski and H. Miller. 1-d queries in 3-d farthest neighbors, simple polygon, motion planning, diame- space. Report ??, Fakulta"t Inform., Univ. Karlsruhe, ter. [2676.2,AAAKSS-CEFN-DAM-91] Karlsruhe,Germany(1985). [1533,AM-1DQ3DS-UK-85] 20 P. K. Agarwal, A. Aggarwal, B. Aronov, S. R. 7 S. Abramowski. Collision avoidance for nonrigid Kosaraju, B. Schieber and S. Suri. Computing external- objects. In Computational Geometry and its Applications, furthestneighboursforasimplepolygon. InProc.1stCanad. Lecture Notes in Computer Science 333, Springer-Verlag Conf. Comput. Geom. (1989), 45. [2676.1, AAAKSS- (1988), 168-179. Keywords: motion planning. [2346, A- CEFNSP-1CCCG-89] CANO-CGA-88] 21 P. K. Agarwal and B. Aronov. Counting facets and 8 D. M. Acketa and J. vZunic´. On the maximal number incidences. Report 90-38, DIMACS, Rutgers Univ., New of edges of convex digital polygons included into a square Brunswick, NJ (1989). Keywords: arrangements, polytopes. grid. InProc.3rdCanad.Conf.Comput.Geom.(1991),215- Other: to appear in Discrete Comput. Geom. [2362, AA- 218. [2730,AZ-MNECDPISG-3CCCG-91] CFI-RU-89] 9 I. Adler, R. Karp and R. Shamir. A simplex variant 22 P. K. Agarwal,B. Aronov,J.O’Rourkeand C. Sche- solving an m×d linear program in O(min(m2,d2)) expected von. Star unfolding of a convex polytope, with applications. number of pivot steps. Report UCB/CSD 83/158, Comput. In Proc. 2nd Scand. Workshop Algorithm Theory (SWAT), Sci. Div., Univ. California, Berkeley, CA (1983). [2000, Lecture Notes in Computer Science 447, Springer-Verlag AKS-SVSMTDLPOMMS2DS2ENPS-UC-83] (1990),251-263. Keywords: motionplanning,shortestpaths, polytopes, diameter, edge sequences, unfolding of polytopes. 10 I.AdlerandN.Megiddo. Asimplexalgorithmwhose [2363,AAOS-SUCPA-2SWAT-90] average number of steps is bounded between two quadratic functions of the smaller dimension. J. ACM ?? (1984), 312- 23 P. K. Agarwal, B. Aronov, M. Sharir and S. Suri. 323. Keywords: average-case analysis, linear programming. Selecting distances in the plane. In Proc. 6th Annu. ACM [1476,AM-SAANSBBTQFSD-JACM-84] Sympos. Comput. Geom. (1990), 321-331. [2205, AASS- SDP-6SCG-90] 11 I.Adler,N.MegiddoandM.J.Todd. Newresultson thebehaviorofsimplexalgorithms. Bull.Amer.Math.Soc.11 24 P.K. Agarwal,H.Edelsbrunner,O. Schwarzkopfand (1984), 378-382. Keywords: average-case analysis, linear E.Welzl. Euclideanminimumspanningtreesandbichromatic programming. [931,AMT-NRBSA-BAMS-84] closest pairs. In Proc. 6th Annu. ACM Sympos. Comput. Geom.(1990),203-210. [2192,AESW-EMSTBCP-6SCG-90] 12 P. K. Agarwal. A deterministic algorithm for parti- tioning arrangements of lines and its applications. In Proc. 25 P. K. Agarwal and J. Matouvsek. Ray shooting and 5th Annu. ACM Sympos. Comput. Geom. (1989), 11-22. parametric search. Manuscript, ?? (1991). Keywords: ray [2128,A-DAPALA-5SCG-89] tracing, range search, intersection, partition trees. [2481, AM-RSPS-??-91] 13 P. K. Agarwal. Geometric algorithms. Report TRCS 85-17, Dept. Comput. Sci., Univ. California, Santa Barbara, 26 P. K. Agarwal and J. Matouvsek. Relative neighbor- CA(1985). Keywords: masterthesis. [1020,A-GA-UC-85] hoodgraphsin3-d. ReportCS-1991-19,Dept.Comput.Sci., DukeUniv.,Durham,NC(1991). Keywords: patternrecogni- 14 P.K.Agarwal. Geometricpartitioninganditsapplica- tion,geometricgraphs. [2479,AM-RNG3D-DU-91] tions. Report CS-1991-27, Dept. Comput. Sci., Duke Univ. (1991). Keywords: randomsampling,partition,arrangement, 27 P. K. Agarwal, J. Matouvsek and S. Suri. Farthest point location. Other: To appear in Discrete and Computa- neighbors, maximum spanning trees and related problems in March4,1992 -- -- 2 ComputationalGeometryBibliography higher dimensions. In Proc. 2nd Workshop Algorithms Data Intersection queries for curved objects. In Proc. 7th Annu. Struct., Lecture Notes in Computer Science 519, Springer- ACM Sympos. Comput. Geom. (1991), 41-50. Keywords: Verlag (1991), 105-116. Keywords: proximity, partition. range searching, partition trees, intersection. [2572, AVO- [2614,AMS-FNMSTRPHD-2WADS-91] IQCO-7SCG-91] 28 P. K. Agarwal and M. Sharir. Applications of a new 41 A.Aggarwal. Theartgalleryproblem: Itsvariations, partitioningscheme. InProc.2ndWorkshopAlgorithmsData applications, and algorithmic aspects. Ph.D. Dissertation, Struct., Lecture Notes in Computer Science 519, Springer- Johns Hopkins Univ., Baltimore, MD (1984). Keywords: Verlag(1991), 379-391. Keywords: randomsampling,range doctoralthesis. [1170,A-AGPVAAA-JHU-84] searching,raytracing,hiddenline/surfaceelimination. [2625, 42 A. Aggarwal, H. Booth, J. O’Rourke, S. Suri and C. AS-ANPS-2WADS-91] K. Yap. Finding minimal convex nested polygons. In Proc. 29 P.K.AgarwalandM.Sharir. Circleshootinginsidea 1st Annu. ACM Sympos. Comput. Geom. (1985), 296-304. simplepolygon. Report90-56,DIMACS,RutgersUniv.,New Keywords: packing, visibility. [793.1, ABOSY-FMCNP- Brunswick,NJ(1990). Keywords: simplepolygon,arcshoot- 1SCG-85] ing. [2365,AS-CSISP-RU-90] 43 A. Aggarwal, H. Booth, J. O’Rourke, S. Suri and C. 30 P. K. Agarwal and M. Sharir. Circularvisibility of a K. Yap. Finding minimal convex nested polygons. Inform. simple polygon from a point. Report 90-61, DIMACS, Comput. 83:1 (October 1989), 98-110. Keywords: packing, Rutgers Univ., New Brunswick, NJ (1990). Keywords: visi- visibility. [793.2,ABOSY-FMCNP-IC-89] bility,simplepolygon. [2366,AS-CVSPP-RU-90] 44 A. Aggarwal, J. S. Chang and C. K. Yap. Minimum 31 P. K. Agarwal and M. Sharir. Counting circular arc areacircumscribingpolygons. VisualComput.1(1985),112- intersections. In Proc. 7th Annu. ACM Sympos. Comput. 117. [1021,ACY-MACP-VC-85] Geom. (1991), 10-20. Keywords: intersection, circles, ran- 45 A.AggarwalandB.Chazelle. Efficientalgorithmfor domsampling. [2569,AS-CCAI-7SCG-91] partitioning a polygon into star-shaped polygons. Report ??, 32 P. K. Agarwal and M. Sharir. Off-line dynamic IBMT.J.WatsonRes.Center,YorktownHeights,NY(1984). maintenanceofthewidthofaplanarpointset. Report90-64, [1171,AC-EAPPSSP-IBMTJWRC-84] DIMACS, Rutgers Univ., New Brunswick, NJ (1990). Key- 46 A. Aggarwal, B. Chazelle, L. Guibas, C. ´O’D´unlaing words: off-line problem, dynamization, width, convex hull. and C. Yap. Parallel computational geometry. Algorithmica [2368,AS-OLDMWPPS-RU-90] 3:3(1988),293-327. [961.2,ACGOY-PCG-A-88] 33 P. K. Agarwal and M. Sharir. Off-line dynamic 47 A. Aggarwal, S. K. Ghosh and R. K. Shyamasundar. maintenance of the width of a planar point set. Comput. Computational complexity of restricted polygon decomposi- Geom. Theory Appl. 1 (1991), 65-78. [2838, AS- tions. In G. T. Toussaint, ed., Computational Geometry, OLDMWPPS-CGTA-91] North-Holland(1987),??-??. [1172,AGS-CCRPD-CG-87] 34 P. K. Agarwaland M. Sharir. Planar geometric loca- 48 A. Aggarwal, L. J. Guibas, J. Saxe and P. Shor. A tion problems. Report 90-58, DIMACS, Rutgers Univ., New lineartimealgorithmforcomputingtheVoronoidiagramofa Brunswick, NJ (1990). Keywords: parametric search, loca- convex polygon. In Proc. 19th Annu. ACM Sympos. Theory tionproblems,arrangements. [2367,AS-PGLP-RU-90] Comput. (1987), 39-45. [191.1, AGSS-LTACVDCP- 35 P. K. Agarwaland M. Sharir. Planar geometric loca- 19STOC-87] tion problems and maintaining the width of a planar set. In 49 A.Aggarwal,L.J.Guibas,J.SaxeandP.W.Shor. A Proc. 2nd ACM-SIAM Sympos. Discrete Algorithms (1991), linear-timealgorithmforcomputingtheVoronoidiagramofa 449-458. Keywords: location problems, width, parametric convexpolygon. DiscreteComput.Geom.4(1989),591-604. searchtechniques. [2564,AS-PGLPMWPS-2SODA-91] [191.2,AGSS-LTACVDCP-DCG-89] 36 P. K. Agarwal and M. Sharir. Red-blue intersection 50 A.Aggarwal,H.Imai,N.Katoh andS.Suri. Finding detectionalgorithms,withapplicationstomotionplanningand k points with minimum diameter and related problems. In collisiondetection. InProc.4thAnnu.ACMSympos.Comput. Proc. 5th Annu. ACM Sympos. Comput. Geom. (1989), 283- Geom. (1988), 70-80. [2043.1, AS-RBIDAAMPCD-4SCG- 291. [2158,AIKS-FKPMDRP-5SCG-89] 88] 51 A.AggarwalandM.Klawe. Applicationsofgeneral- 37 P. K. Agarwal and M. Sharir. Red-blue intersection izedmatrixsearchingtogeometricalgorithms. Manuscript,?? detectionalgorithms,withapplicationstomotionplanningand (19??). [1990,AK-AGMSGA-??-??] collision detection. SIAM J. Comput. 19 (1990), 297-321. Keywords: intersection. [2043.2, AS-RBIDAAMPCD- 52 A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial SIAMJC-90] andA.Wigderson. Alowerboundontheareaofpermutation layouts. Algorithmica6(1991), 241-255. [2538.2, AKLLW- 38 P. K. Agarwal, M. Sharir and P. Shor. Sharp upper LBAPL-A-91] andlowerboundsonthelengthofgeneralDavenport-Schinzel sequences. J. Combin. Theory Ser. A 52 (1989), 228-274. 53 A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial Keywords: Davenport-Schinzel sequences, Ackermann’s and A. Wigderson. Multi-layer grid embeddings. In Proc. function. [2372,ASS-SULBLGDSS-JCTA-89] 26th Annu. IEEE Sympos. Found. Comput. Sci. (1985), 186- 196. [2538.1,AKLLW-MLGE-26FOCS-85] 39 P. K. Agarwal and M.-T. Shing. Efficient special cases of rectilinear Steiner trees. Networks 20 (1990), 453- 54 A.Aggarwal,M.M.Klawe,S.Moran,P.ShorandR. 485. Keywords: Steinertrees. [1546,AS-ESCRST-N-90] Wilber. Geometric applications of a matrix searching algo- rithm. In Proc. 2nd Annu. ACM Sympos. Comput. Geom. 40 P. K. Agarwal, M. van Kreveld and M. Overmars. (1986),285-292. [672.1,AKMSW-GAMSA-2SCG-86] March4,1992 -- -- ComputationalGeometryBibliography 3 55 A.Aggarwal,M.M.Klawe,S.Moran,P.ShorandR. T.Akama. Seealso2627[2329]. Wilber. Geometric applications of a matrix-searching algo- 69 H. Akima. Algorithm 526: Bivariate interpolation rithm. Algorithmica 2 (1987), 195-208. [672.2, AKMSW- and smooth surface fitting for irregularly distributed data GAMSA-A-87] points. ACMTrans.Math.Softw.4:2(1978),160-164. [1595, 56 A.AggarwalandR.Melville. Fastcomputationofthe A-A5BISSFIDDP-ACMTMS-78] modalityofpolygons. J.Algorithms7(1986),369-381. [337, 70 H. Akima. On estimating partial derivatives for AM-FCMP-JA-86] bivariate interpolation of scattered data. Rocky Mountain J. 57 A. Aggarwal, S. Moran, P. Shor and S. Suri. An Math.14:1(1984),41-52. [1599,A-EPDBISD-RMJM-84] O(nloglogn) algorithm for finding the closest visible vertex S.Akl. Seealso2237[2226]. pair in two simple polygons. Report ??, IBM T. J. Watson Res. Center, Yorktown Heights, NY (June 1987). [638, 71 S. G. Akl. A constant-time parallel algorithm for AMSS-ONLLNAFCVVPTSP-IBMTJWRC-87] computing convex hulls. BIT 22 (1982), 130-134. [10, A- CTPACCH-BIT-82] 58 A.Aggarwal,S.Moran,P.W.ShorandS.Suri. Com- puting the minimum visible vertex distance between two 72 S.G.Akl. Ananalysisofvariousaspectsofthetrav- polygons. In Proc. 1st Workshop Algorithms Data Struct., eling salesman problem. Ph.D. Thesis, School Comput. Sci., Lecture Notes in Computer Science 382, Springer-Verlag McGill Univ., Montreal, PQ (1978). [7, A-AVATSP-MGU- (1989),115-134. [2298,AMSS-CMVVDBTP-1WADS-89] 78] 59 A.AggarwalandJ.Park. Notesonsearchinginmul- 73 S. G. Akl. Comments on: G. Manacher, an applica- tidimensional monotone arrays. In Proc. 29th Annu. IEEE tionofpatternmatchingtoaproblemingeometricalcomplex- Sympos. Found. Comput. Sci. (1988), 497-512. [2097, AP- ity. Inform. Process. Lett. 7:2 (1978), 86. Keywords: NSMMA-29FOCS-88] polygon similarity, affine maps. [394.2, A-CGMAPMPGC- IPL-78] 60 A. Aggarwal, P. Raghavan and P. Tiwari. Lower bounds for closest pair and related problems in simple 74 S. G. Akl. Corrigendum on convex hull algorithms. polygons. Report ??, IBM T. J. Watson Res. Center, York- Inform. Process. Lett. 10:3 (1980), 168. [1174, A-CCHA- town Heights, NY (1987). [185, ART-LBCPRPSP- IPL-80] IBMTJWRC-87] 75 S.G. Akl. On maximaltriangulations, optimal draw- 61 A.AggarwalandS.Suri. Fastalgorithmsforcomput- ings and Hamilton cycles. Report 78-67, Dept. Comput. ing the largest empty rectangle. In Proc. 3rd Annu. ACM Inform. Sci., Queen’s Univ., Kingston, ON (1978). [8, A- Sympos. Comput. Geom. (1987), 278-290. [639, AS- MTODHC-QU-78] FACLER-3SCG-87] 76 S.G. Akl. Optimalalgorithmsforcomputingconvex 62 A. Aggarwal and J. Wein. Computational geometry. hulls and forsorting. Computing33(1984), 1-11. [1799, A- Report RSS-3, Lab. Comput. Sci., Massachusetts Inst. Tech. OACCHS-C-84] (1988). Keywords: lecture notes. Other: lecture notes for 77 S. G. Akl. Optimal parallel algorithms for selection, course18.409. [2756,AW-CG-MIT-88] sorting and computing convex hulls. In G. T. Toussaint,ed., A. Aggarwal. See also 19[2676.2], 20[2676.1], ComputationalGeometry,North-Holland,Amsterdam(1985), 549[961.1],758[186],2094[977]. 1-22. [1798,A-OPASSCCH-CG-85] 63 A.V.Aho,M.R.GareyandF.K.Hwang. Rectilinear 78 S. G. Akl. Two remarkson a convex hull algorithm. Steiner trees: efficient special case algorithms. Networks 7 Inform. Process. Lett. 8:2 (1979), 108-109. Keywords: con- (1977),37-58. [1,AGH-RSTESCA-N-77] vexhull,counterclockwisetest,angle test,geometricalprimi- tives. [9,A-TRCHA-IPL-79] 64 A. V. Aho, J. E. Hopcroft and J. D. Ullman. The Design and Analysis of Computer Algorithms, Addison- 79 S.G.Akl,K.QuiandI.Stojmenovic. Computational Wesley,Reading,MA(1974). [1312,AHU-DACA-AW-74] geometry on the star and pancake networks. In Proc. 3rd Canad.Conf.Comput.Geom. (1991), 252-255. [2738, AQS- 65 A. V. Aho and J. D. Ullman. Optimal partial-match CGSPN-3CCCG-91] retrievalwhenfieldsareindependentlyspecified. ACMTrans. Database Syst. 4 (1979), 168-179. [2, AU-OPMRFIS- 80 S. G. Akl and G. T. Toussaint. A fast convex hull ACMTDS-79] algorithm. Inform. Process. Lett. 7:5 (1978), 219-222. [12, AT-FCHA-IPL-78] 66 D.V.AhujaandS.A.Coons. Geometryforconstruc- tion and display. IBM Syst. J. 7 (1968), 188-205. [3, AC- 81 S. G. Akl and G. T. Toussaint. Addendum to ‘‘An GCD-IBMSJ-68] improvedalgorithmtocheckforpolygonsimilarity’’. Inform. Process. Lett. 8:3 (1979), 157-158. [11.2, AT-AIACPS-IPL- 67 N. Ahuja. Dot pattern processing using Voronoi 79] polygons as neighborhoods. In Proc. Internat. Conf. Pattern Recogn., Miami Beach, FL (1980), 1122-1127. [4, A- 82 S. G. Akl and G. T. Toussaint. An improved algo- DPPVPN-ICPR-80] rithmtocheckforpolygonsimilarity. Inform.Process.Lett.7 (1978),127-128. [11.1,AT-IACPS-IPL-78] 68 N. Ahuja, R. T. Chien, R. Yen and N. Birdwell. Interference detection and collision avoidance among three 83 S.G. Akl and G. T. Toussaint. Efficient convex hull dimensionalobjects. In Proc. 1stNat. Conf.ArtificialIntell., algorithms for pattern recognition applications. In Proc. 4th Palo Alto,CA(1980),44-48. [5,ACYB-IDCATDO-1NCAI- Internat. Conf. Pattern Recogn., Kyoto, Japan (1978), 483- 80] 487. Keywords: convex hull, simple polygon, average-case analysis, average size of convex hull, empirical analysis, March4,1992 -- -- 4 ComputationalGeometryBibliography Graham’sscan. [13,AT-ECHAPRA-4ICPR-78] A-SSAG-AMM-46] S.G.Akl. Seealso2696[612]. 99 D.C.S.AllisonandM.T. Noga. Someperformance tests of convex hull algorithms. BIT 24 (1984), 2-13. [861, 84 V. Akman. An algorithm for determining an opaque AN-SPTCHA-BIT-84] minimalforestofaconvexpolygon. Inform.Process.Lett.24 (1987), 193-198. Keywords: triangulation, Steiner trees, 100 D. C. S. Allison and M. T. Noga. The L traveling 1 minimumspanningtrees. [1567,A-ADOMFCP-IPL-87] salesmanproblem. Inform.Process.Lett.18(1984),195-199. [896,AN-LS1TSP-IPL-84] 85 V. Akman. Unobstructed Shortest Paths in PolyhedralEnvironments,LectureNotesinComputerScience 101 N. Alon, D. Haussler and E. Welzl. Partitioning and 251,Springer-Verlag(1987). [1311,A-USPPE-SV-87] geometric embedding of range spaces of finite Vapnik- Chervonenkis dimension. In Proc. 3rd Annu. ACM Sympos. V.Akman. Seealso1088[1319],1089[1246]. Comput. Geom. (1987), 331-340. [1281, AHW- 86 T. Akutsu, Y. Aoki, S. Hasegawa, H. Imai and T. PGERSFVCD-3SCG-87] Tokuyama. Thesumofsmallerendpointdegreeoveredgesof 102 N. Alon,M. Katchalski and W. R. Pulleyblank. Cut- graphs and its applications to geometric problems. In Proc. tingdisjointdisksbystraightlines. DiscreteComput.Geom.4 3rd Canad. Conf. Comput. Geom. (1991), 145-148. [2714, (1989),239-243. [2757,AKP-CDDSL-DCG-89] AAHIT-SSEDOEGAGP-3CCCG-91] S.R.Alpert. Seealso1244[1460]. R.Alami. Seealso1626[2652]. 103 H. Alt, B. Behrends and J. Bl"omer. Approximate 87 A. Albrecht. On the circuit complexity of planar matchingofpolygonalshapes. InProc.7thAnnu.ACMSym- objects. In Proc. 7th Internat. Conf. Pattern Recogn., Mont- pos. Comput. Geom. (1991), 186-193. Keywords: matching, real,PQ(1984),??-??. [1326,A-CCPO-7ICPR-84] polygons,approximation. [2588,ABB-AMPS-7SCG-91] 88 A. Albrecht. On the VLSI complexity of some 104 H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. geometricalcomputationproblems. Report86,SektionMath., N"aher,S.SchirraandC.Uhrig. Approximatemotionplanning HumboldtUniv.,Berlin(1984). [1022,A-VCSGCP-HU-84] and the complexity of the boundary of the union of simple 89 P.Alevizos,J.D.BoissonnatandF.P.Preparata. An geometricfigures. InProc.6thAnnu.ACMSympos.Comput. optimalalgorithmfortheboundaryofacellinaunionofrays. Geom. (1990), 281-289. [2201, AFKMNSU-AMPCBUSGF- Algorithmica 5 (1990), 573-590. [2478.1, ABP-OABCUR- 6SCG-90] A-90] 105 H.AltandK.Mehlhorn. Searchingsemisortedtables. 90 P.Alevizos,J.D.BoissonnatandF.P.Preparata. An SIAM J. Comput. 14 (1985), 840-848. [193, AM-SST- optimalalgorithmfortheboundaryofacellinaunionofrays: SIAMJC-85] corrigendum. Algorithmica 6 (1991), 292-293. [2478.2, 106 H. Alt, K. Mehlhorn and J. I. Munro. Partial match ABP-OABCURC-A-91] retrievalin implicit data structures. Inform.Process. Lett.19 91 P.Alevizos,J.-D.BoissonnatandM.Yvinec. On the (1984),61-65. [15,AMM-PMRIDS-IPL-84] orderinducedbyasetofrays,withapplicationtotheprobing 107 H. Alt, K. Mehlhorn, H. Wagener and E. Welzl. of non-convex polygons. Manuscript, INRIA Sophia- Congruence, similarity and symmetries of geometric objects. Antipolis, Valbonne, France (1989). Keywords: robotics, In Proc. 3rd Annu. ACM Sympos. Comput. Geom. (1987), probing, shape, worst-case analysis, rays, polygons, two- 308-315. [1273.1,AMWW-CSSGO-3SCG-87] dimensional. [2089,ABY-OISRAPNCP-INRIASA-89] 108 H. Alt, K. Mehlhorn, H. Wagener and E. Welzl. 92 P. D. Alevizos, J.-D. Boissonnat and M. Yvinec. An Congruence, similarity and symmetries of geometric objects. optimal O(nlogn) algorithm for contour reconstruction from Discrete Comput. Geom. 3 (1988), 237-256. [1273.2, rays. In Proc. 3rd Annu. ACM Sympos. Comput. Geom. AMWW-CSSGO-DCG-88] (1987),162-170. [1224,ABY-OONLNACRR-3SCG-87] 109 H. Alt and E. Welzl. Visibility graphs and obstacle- 93 N.A.AlexandridisandP.D.Tsanakas. Anencoding avoiding shortest paths. Zeitschrift fu"r Operations Research scheme for the efficient representation of hierarchical image 32(1988),145-164. [2527,AW-VGOASP-ZOR-88] structures. Inform.Process.Lett.25(1987), 199-206. [1099, AT-ESERHIS-IPL-87] H.Alt. Seealso1872[198.1],1873[198.2]. 94 P. Alexandroff and H. Hopf. Topologie I, 110 W.Altherr. Analgorithmforenumeratingthevertices Grundlehren der math 45, Julius Springer, Berlin (1935). of a convex polyhedron. Computing 15 (1975), 181-193. [1748,AH-TI-JS-35] [1480,A-AEVCP-C-75] 95 A. D. Alexandrov. Konvexe Polyeder, Akademie- 111 E. G. Anagnostou, L. J. Guibas and V. G. Polimenis. Verlag,Berlin(1958). [1749,A-KP-AV-58] Topologicalsweepinginthreedimensions. InProc.1stAnnu. SIGAL Internat. Sympos. Algorithms, Lecture Notes in Com- 96 P. Alfeld. A discrete C1 interpolant for tetrahedral puter Science 450, Springer-Verlag (1990), 310-317. Key- data. Rocky Mountain J. Math. 14 (1984), 5-16. [1330, A- words: topological sweep, three-dimensional. [2472, AGP- DCS1ITD-RMJM-84] TSTD-1SIGALISA-90] 97 P.AlfeldandR.E.Barnhill. AtransfiniteC2interpo- 112 K. R. Anderson. A reevaluation of an efficient algo- lant over triangles. Rocky Mountain J. Math. 14:1 (1984), rithm for determining the convex hull of a finite planar set. 17-39. [1598,AB-TCS2IOT-RMJM-84] Inform. Process. Lett. 7 (1978), 53-55. [16, A- 98 C. B. Allendoerfer. ‘‘Slope’’ in solid analytic READCHFPS-IPL-78] geometry. Amer. Math. Monthly 53 (1946), 241-247. [1593, March4,1992 -- -- ComputationalGeometryBibliography 5 T.Anderson. Seealso1555[1473]. 125 E. M. Arkin, R. Connelly and J. S. B. Mitchell. On monotone paths among obstacles, with applications to plan- 113 A. M. Andrew. Another efficient algorithm for con- ning assemblies. In Proc. 5th Annu. ACM Sympos. Comput. vex hulls in two dimensions. Inform. Process. Lett. 9:5 Geom.(1989),334-343. Keywords: pathplanning,monotoni- (1979),216-219. [17,A-AEACHTD-IPL-79] city, assembly, visibility, separability. [2163, ACM- Y.P.Aneja. Seealso1484[2276]. MPOAPA-5SCG-89] 114 S. Ansaldi, L. De Floriani and B. Falcidieno. 126 E.M.Arkin,D.Halperin,K.Kedem,J.S.B.Mitchell Geometricmodelingofsolidobjectsbyusingafaceadjacency andN.Naor. Arrangementsofsegmentsthatshareendpoints: graph representation. In Proc. SIGGRAPH ’85, Comput. singlefaceresults. InProc.7thAnnu.ACMSympos.Comput. Graph. 19:3 (1985), 131-139. [1457, ADF-GMSOFAGR- Geom. (1991),324-333. Keywords: arrangements,segments, SIGGRAPH85-85] Davenport-Schinzel sequences, zone theorems. [2604, AHKMN-ASSESFR-7SCG-91] Y.Aoki. Seealso86[2714]. 127 E.M.Arkin,K.Kedem,J.S.B.Mitchell,J.Sprinzak 115 H. Aonuma, H. Imai, K. Imai and T. Tokuyama. and M. Werman. Matching points into noise regions: com- Maximin location of convex objects in a polygonand related binatorial bounds and algorithms. In Proc. 2nd ACM-SIAM dynamicVoronoidiagrams. InProc.6thAnnu.ACMSympos. Sympos. Discrete Algorithms (1991), 42-51. Keywords: Comput. Geom. (1990), 225-234. [2195, AIIT- matching, similarity. [2558, AKMSW-MPNRCBA-2SODA- MLCOPRDVD-6SCG-90] 91] 116 A. Appel and P. M. Will. Determining the three- 128 E. M. Arkin, S. Khuller and J. S. B. Mitchell. dimensional convex hull of a polyhedron. IBM J. Res. Geometricknapsackproblems. In Proc.2ndWorkshopAlgo- Develop. ?? (1976), 590-611. [18, AW-DTDCHP-IBMJRD- rithms Data Struct., Lecture Notes in Computer Science 519, 76] Springer-Verlag (1991), 165-176. [2617, AKM-GKP- 117 D. Applegate and R. Kannan. Local expansion of 2WADS-91] vertex-transitive graphs and random generation in finite 129 E.M.Arkin,S.KhullerandJ.S.B.Mitchell. Optimal groups. In Proc. 23rd Annu. ACM Sympos. Theory Comput. enclosure problems. In Proc. 1st Canad. Conf. Comput. (1991),164-174. Keywords: approximation,volume,convex. Geom. (1989), 36. Keywords: partitioning, enclosure, knap- [2490,AK-LEVTGRGFG-23STOC-91] sack, optimization. Other: to appear in Algorithmica, 1991. 118 J. Ara´oz and W. H. Cunningham. Reductions to 1- [2667,AKM-OEP-1CCCG-89] matching polyhedra. Networks 13 (1983), 455-473. [991, 130 E.M.Arkin,J.S.B.MitchellandC.D.Piatko. Bicri- AC-R1MP-N-83] teriashortestpathproblemsintheplane. InProc.3rdCanad. 119 C.ArcelliandL.Cordella. Concavitypointdetection Conf.Comput.Geom.(1991),153-156. [2716,AMP-BSPPP- byiterativearrays. Comput.Graph.ImageProcess.3(1974), 3CCCG-91] 34-47. [1802,AC-CPDIA-CGIP-74] 131 E. M. Arkin, J. S. B. Mitchell and K. Zikan. Algo- 120 C. Arcelli and S. Levialdi. Concavity extraction by rithms for point matching problems. Manuscript, School parallel processing. IEEE Trans. Syst. Man Cybern. SMC-1 Oper. Res. Indust. Engrg., Cornell Univ. (1989). Keywords: (1971),394-396. [1803,AL-CEPP-IEEETSMC-71] matching,computervision. [2410,AMZ-APMP-CU-89] 121 C. Arcelli and G. Sanniti de Baja. Polygonal cover- 132 D. B. Arnold and W. J. Milne. The use of Voronoi ing and concavity tree of binary digital pictures. In M. H. tessellations in processing soil survey results. IEEE Comput. Hamza and S. G. Tzafestas, eds., Proc. Internat. Sympos. Graph.Appl.4(1984),22-28. Keywords: application, Voro- Measurement &Control(MECO’78),PanhellenicSocietyof noi diagrams, subdivision. [1177, AM-UVTPSSR- Mechanical & Electrical Engineers, Athens (1978), 292-297. IEEECGA-84] [1804,AS-PCCTBDP-ISMC-78] 133 B.Aronov. OnthegeodesicVoronoidiagramofpoint A.S.Argon. Seealso1959[2239]. sites in a simple polygon. In Proc. 3rd Annu. ACM Sympos. Comput. Geom. (1987), 39-49. [1186.1, A-GVDPSSP- E.Ariel-Sheffi. Seealso2479[1402]. 3SCG-87] 122 E. Arkin. Beautification is hard. Technical Report 134 B.Aronov. OnthegeodesicVoronoidiagramofpoint 818, School Oper. Res. Indust. Engrg., Cornell Univ., Ithaca, sites in a simplepolygon. Algorithmica4:1(1989), 109-140. NY(1988). Keywords: clustering. [2528,A-BH-CU-88] [1186.2,A-GVDPSSP-A-89] 123 E. Arkin and J. S. B. Mitchell. An optimal visibility 135 B.Aronov,B.Chazelle,H.Edelsbrunner,L.J.Guibas algorithm for a simple polygon with star-shaped holes. and M. Sharir. Slimming down by adding; selecting heavily TechnicalReport746,SchoolOper.Res.Indust.Engrg.,Cor- covered points. In Proc. 6th Annu. ACM Sympos. Comput. nell Univ., Ithaca, NY (1987). Keywords: visibility, hidden Geom. (1990), 116-127. [2183, ACEGS-SDASHCP-6SCG- line/surface elimination, plane-sweep. [1012, AM- 90] OVASPSSH-CU-87] 136 B. Aronov, B. Chazelle, H. Edelsbrunner, L. J. Gui- 124 E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. bas, M. Sharir and R. Wenger. Points and triangles in the Kedem and J. S. B. Mitchell. An efficiently computable plane and halving planes in space. In Proc. 6th Annu. ACM metric for comparing polygonal shapes. In Proc. 1st ACM- Sympos. Comput.Geom.(1990),112-115. [2182,ACEGSW- SIAM Sympos. Discrete Algorithms (1990), 129-137. Key- PTPHPS-6SCG-90] words: matching, shape, polygons. [2317, ACHKM- ECMCPS-1SODA-90] 137 B.Aronov,H.Edelsbrunner,L.GuibasandM.Sharir. Improvedboundsonthecomplexityofmanyfacesinarrange- March4,1992 -- -- 6 ComputationalGeometryBibliography ments of segments. Report 459, Dept. Comput. Sci., New ning, geometric transformations, visibility, arrangements. York Univ. (July 1989). Keywords: arrangements,complex- [324,AAI-SPBTSP-IPL-87] ity of faces, random sampling. [2373, AEGS-IBCMFAS- 151 Ta. Asano, Te. Asano and R. Y. Pinter. Polygon tri- NYU-89] angulation: efficiency and minimality. J. Algorithms 7 138 B.Aronov,P.Erdo"s,W.Goddard,D.J.Kleitman,M. (1986), 221-231. Keywords: lower bounds, design of algo- Klugerman,J.PachandL.J.Schulman. Crossingfamilies. In rithms,triangulation. [976,AAP-PTEM-JA-86] Proc. 7th Annu. ACM Sympos. Comput. Geom. (1991), 351- 152 Ta.Asano,M.Edahiro,H.Imai,M.IriandK.Murota. 356. Keywords: partition. [2607,AEGKKPS-CF-7SCG-91] Practical use of bucketing techniques in computational 139 B. Aronov, S. J. Fortune and G. Wilfong. The geometry. In G. T. Toussaint, ed., Computational Geometry, furthest-site geodesic Voronoi diagram. In Proc. 4th Annu. North-Holland (1985), 153-195. Keywords: survey paper, ACM Sympos. Comput. Geom. (1988), 229-240. [2058, implementingalgorithms,optimization,bucketing,matchings, AFW-FSGVD-4SCG-88] Voronoi diagrams, range search, point location, quad trees. 140 B.Aronov,J.MatouvsekandM.Sharir. Onthesumof [1024,AEIIM-PUBTCG-CG-85] squares of cell complexities in hyperplane arrangements. In 153 Ta.Asanoand T. Hirata. Edge-contractionproblems. Proc. 7th Annu. ACM Sympos. Comput. Geom. (1991), 307- J. Comput. Syst. Sci. 26 (1983), 197-208. Keywords: NP- 313. Keywords: arrangements, polytopes, hyperplanes. completeness,graphtheory. [927,AH-ECP-JCSS-83] [2602,AMS-SSCCHA-7SCG-91] 154 Ta. Asano, M. Sato and T. Ohtsuki. Computational 141 B. Aronov and J. O’Rourke. Nonoverlap of the star geometry algorithms. In T. Ohtsuki, ed., Layout Design and unfolding. In Proc. 7thAnnu. ACM Sympos. Comput.Geom. Verification, North-Holland (1986), 295-347. Keywords: (1991),105-114. Keywords: polytopes,shortestpaths,Voro- VLSI design, priority search trees, intersection, rectangles. noidiagrams,edgesequences. [2579,AO-NSU-7SCG-91] [517,ASO-CGA-LDV-86] 142 B.AronovandM.Sharir. Onthezoneofasurfacein Ta. Asano. See also 169[1180], 906[1609], ahyperplanearrangement. InProc.2ndWorkshopAlgorithms 907[1066], 908[1262.1], 909[1262.2], 1417[1940], Data Struct., Lecture Notes in Computer Science 519, 1418[1315],1419[1314],1420[839],1421[967]. Springer-Verlag (1991), 13-19. Keywords: arrangements, 155 Te.Asano. Anewcompactionalgorithmforbuilding hyperplanes. [2610,AS-ZSHA-2WADS-91] block LSI using block packing technique. Technical Report 143 B.AronovandM.Sharir. Trianglesinspaceorbuild- CAS85-158, IECE of Japan (1986). [445, A-NCABBLBPT- ing(andanalyzing)castlesintheair. InProc.4thAnnu.ACM IECEJ-86] Sympos. Comput. Geom. (1988), 381-391. Keywords: three- 156 Te. Asano. Accuracy of digital images of lines and dimensional,arrangements. [2070.1,AS-TSBACA-4SCG-88] disks. Technical Report COMP86-6, IECE of Japan (1986). 144 B.AronovandM.Sharir. Trianglesinspaceorbuild- Keywords: design of algorithms, discrete geometry, convex ing (and analyzing) castles in the air. Combinatorica 10:2 hull,worst-caseanalysis. [444,A-ADILD-IECEJ-86] (1990), 137-173. Keywords: three-dimensional, arrange- 157 Te. Asano. An algorithm for computing every angle ments. [2070.2,AS-TSBACA-C-90] ofmovableseparabilityoftwopolygons. Trans.IECEJapan B. Aronov. See also 19[2676.2], 20[2676.1], J69-A (1986), 1162-1165. Keywords: design of algorithms, 21[2362],22[2363],23[2205]. visibility, convex hull, path planning. Other: in Japanese. [299,A-ACEAMSTP-TIECEJ-86] 145 E. Artzy, G. Frieder and G. T. Herman. The theory, design, implementation, and evaluation of 3-d surface detec- 158 Te. Asano. An efficient algorithm for computing the tion algorithms. Comput. Graph. Image Process. 15 (1981), k-reachability region from a point. Trans. IECE Japan E68 1-24. [19,AFH-TDIE3DSDA-CGIP-81] (1985), 560-562. Keywords: design of algorithms, VLSI design, visibility, plane-sweep. [1179, A-EACKRRP- 146 Ta. Asano and Te. Asano. Minimum partition of TIECEJ-85] polygonal regions into trapezoids. In Proc. 24thAnnu. IEEE Sympos. Found. Comput. Sci. (1983), 233-241. [1934, AA- 159 Te. Asano. An efficient algorithm for computing the MPPRT-24FOCS-83] reachability polygon from a point: rectilinear case. In Proc. ISCAS(1985),1293-1296. [1329,A-EACRPPRC-ISCAS-85] 147 Ta.AsanoandTe.Asano. Voronoidiagramforpoints in a simple polygon. Manuscript, ?? (1987). [1442, AA- 160 Te. Asano. An efficient algorithm for finding the VDPSP-??-87] region reachable within k bends. Trans. IECE Japan E68 (1985), 831-835. Keywords: design of algorithms, VLSI 148 Ta. Asano, Te. Asano, L. J. Guibas, J. Hershberger design, worst-case analysis, visibility. [265, A- and H. Imai. Visibility of disjoint polygons. Algorithmica 1 EAFRRWKB-TIECEJ-85] (1986),49-63. Keywords: designofalgorithms,datastructur- ing, visibility, path planning, geometric transformations, 161 Te.Asano. Anefficientalgorithmforfindingthevisi- arrangements. [951,AAGHI-VDP-A-86] bilitypolygonforapolygonalregionwithholes. Trans.IECE JapanE68(1985),560-562. Keywords: designofalgorithms, 149 Ta. Asano, Te. Asano and H. Imai. Partitioning a computer graphics, reporting, visibility, hidden line/surface polygonalregionintotrapezoids. J.ACM33(1986),290-312. elimination,plane-sweep. [1178,A-EAFVPPRH-TIECEJ-85] Keywords: approximation, dynamic programming, triangula- tion. [1023,AAI-PPRT-JACM-86] 162 Te.Asano. Dividing a simplepolygonintotwoterri- tories. Trans. IECE Japan E69 (1986), 521-523. Keywords: 150 Ta. Asano, Te. Asano and H. Imai. Shortest path design of algorithms, visibility, decomposition, operations between two simple polygons. Inform. Process. Lett. 24 research. [309,A-DSPTT-TIECEJ-86] (1987),285-288. Keywords: designofalgorithms,pathplan- March4,1992 -- -- ComputationalGeometryBibliography 7 163 Te.Asano. Generatingand countingvalidpatternsin 177 Te. Asano and G. T. Toussaint. Computing the geo- routes between two points. Graphs Combin. 2 (1986), 9-13. desic center of a simple polygon. Technical Report Keywords: counting, VLSI design, path planning. [637, A- COMP86-24, IECE of Japan (1986). [446, AT-CGCSP- GCVPRBTP-GC-86] IECEJ-86] 164 Te.Asano. Onminimumwidthpackingofrectilinear 178 Te.AsanoandH.Umeo. Systolicalgorithmsforcom- blocks. Trans.IECEJapanE68(1985),647-649. Keywords: puting the visibility polygon and triangulation of a polygonal designofalgorithms,plane-sweep,graphtheory,VLSIdesign, region. TechnicalReportCOMP86-7, IECE of Japan (1986). packing. [43,A-MWPRB-TIECEJ-85] Keywords: parallelcomputation,designofalgorithms,visibil- ity,triangulation. [439,AU-SACVPTPR-IECEJ-86] 165 Te. Asano. Parallel global route. Japanese Journal 23(1982),443-450. [1446,A-PGR-JJ-82] Te.Asano. Seealso146[1934],147[1442],148[951], 149[1023],150[324],151[976],706[1218]. 166 Te. Asano. Rectilinear shortest paths in a rectilinear simple polygon. Trans. IECE Japan E69 (1985), 750-758. 179 P. Ash, E. Bolker, H. Crapo and W. Whiteley. Con- Keywords: design of algorithms, minimum spanning trees, vex polyhedra,Dirichlettesselations, and spiderwebs. In M. decomposition,pointlocation. [267,A-RSPRSP-TIECEJ-85] Senechal and G. Fleck, eds., Shaping Space: A polyhedral approach, Birkha"user Verlag, Boston, MA (1984), ??-??. 167 Te. Asano. Routes between two points. Japanese [1497,ABCW-CPDTSW-SSA-84] Journal23(1982),576-578. [1443,A-RBTP-JJ-82] 180 P. F. Ash and E. D. Bolker. Recognizing Dirichlet 168 Te. Asano. Two layer routing problem with large tessellations. Geom. Dedicata 19 (1985), 175-206. Key- vias. Technical Report CAS86-198, IECE of Japan (1987). words: Voronoidiagrams. [2755,AB-RDT-GD-85] Keywords: designofalgorithms,VLSIdesign,pathplanning, decomposition, plane-sweep, priority search trees, reporting, 181 M. J. Atallah. A linear time algorithm for the Haus- pointlocation. [509,A-TLRPLV-IECEJ-87] dorff distance between convex polygons. Inform. Process. Lett.17(1983),207-209. [891,A-LTAHDBCP-IPL-83] 169 Te. Asano, Ta. Asano and Y. Ohsuga. Partitioning a polygonalregionintoaminimumnumberoftriangles. Trans. 182 M. J. Atallah. A matching problem in the plane. J. IECE Japan E67:4 (1984), 232-233. Keywords: approxima- Comput.Syst.Sci.31(1985),63-70. [941,A-MPP-JCSS-85] tion, dynamic programming, triangulation. [1180, AAO- 183 M. J. Atallah. Checking similarity of planar figures. PPRMNT-TIECEJ-84] Internat. J. Comput. Inform. Sci. 13 (1984), 279-290. [2449, 170 Te. Asano, B. Bhattacharya, J. M. Keil and F. Yao. A-CSPF-IJCIS-84] Clusteringalgorithmsbasedonminimumandmaximumspan- 184 M. J. Atallah. Computing the convex hull of line ningtrees. InProc.4thAnnu.ACMSympos.Comput.Geom. intersections. J. Algorithms 7 (1986), 285-288. [979, A- (1988),252-257. Keywords: clusteranalysis,minimumspan- CCHLI-JA-86] ning trees, diameter, partition. [1996, ABKY-CABMMST- 4SCG-88] 185 M. J. Atallah. On symmetry detection. IEEE Trans. Comput.C-34(1985),663-666. [1616,A-SD-IEEETC-85] 171 Te. Asano, L. J. Guibas and T. Tokuyama. Walking on an arrangement topologically. In Proc. 7th Annu. ACM 186 M.J.Atallah. Somedynamiccomputationalgeometry Sympos. Comput. Geom. (1991), 297-306. Keywords: problems. Comput. Math. Appl. 11 (1985), 1171-1181. arrangements,lines. [2601,AGT-WAT-7SCG-91] [1181,A-SDCGP-CMA-85] 172 Te. Asano, J. Hershberger, J. Pach, E. Sontag, D. 187 M. J. Atallah and C. Bajaj. Efficient algorithms for Souvaine and S. Suri. Separating bi-chromatic points by commontransversals. Inform.Process.Lett.25(1987),87-91. parallel lines. In Proc. 2nd Canad. Conf. Comput. Geom. [885,AB-EACT-IPL-87] (1990),46-49. [2221,AHPSSS-SBCPPL-2CCCG-90] 188 M. J. Atallah, P. Callahan and M. T. Goodrich. P- 173 Te.Asano,M.E.Houle,H.ImaiandK.Imai. Auni- complete geometric problems. In Proc. 2nd ACM Sympos. fiedlinear-spaceapproachtogeometricminimaxproblems. In Parallel Algorithms Architect. (1990), 317-326. [2811, Proc.2ndCanad.Conf.Comput.Geom.(1990),20-23. [2215, ACG-PCGP-2SPAA-90] AHII-ULSAGMP-2CCCG-90] 189 M. J.Atallah and D. Z. Chen. Optimal parallel algo- 174 Te. Asano, H. Imai and K. Imai. Clustering/hashing rithmforvisibilityofasimplepolygonfromapoint. InProc. pointsintheplanewithmaxmincriteria. InProc.1stCanad. 5th Annu. ACM Sympos. Comput. Geom. (1989), 114-123. Conf. Comput. Geom. (1989), 15. [2646, AII-CHPPMC- [2139,AC-OPAVSPP-5SCG-89] 1CCCG-89] 190 M. J. Atallah and D. Z. Chen. Parallel rectilinear 175 Te.AsanoandT.Tokuyama. Algorithmsforproject- shortest paths with rectangular obstacles. Comput. Geom. ingpointstogive the mostuniformdistributionwithapplica- Theory Appl.1 (1991), 79-113. [2839, AC-PRSPRO-CGTA- tion to hashing. In Proc. 1st Annu. SIGAL Internat. Sympos. 91] Algorithms, Lecture Notes in Computer Science 450, 191 M.J.Atallah,R.ColeandM.T.Goodrich. Cascading Springer-Verlag (1990), 300-309. [2471, AT- divide-and-conquer: A technique for designing parallel algo- APPGMUDAH-1SIGALISA-90] rithms. In Proc. 28th Annu. IEEE Sympos. Found. Comput. 176 Te. Asano and T. Tokuyama. Circuit partitioning Sci.(1987),??-??. [901.1,ACG-CDCTDPA-28FOCS-87] algorithms:graphmodelversusgeometrymodel. InProc.2nd 192 M.J.Atallah,R.ColeandM.T.Goodrich. Cascading Annu. SIGAL Internat. Sympos. Algorithms, Lecture Notes in divide-and-conquer: A technique for designing parallel algo- Computer Science 557, Springer-Verlag (1991), 94-103. rithms. SIAM J. Comput. 18 (1989), 499-532. Keywords: [2845,AT-CPAGMVGM-2SIGALISA-91] parallelcomputation,decomposition,rangesearch,pointloca- March4,1992 -- -- 8 ComputationalGeometryBibliography tion, visibility, domination, points, lines, divide-and-conquer, cal congruence. J. Algorithms 8 (1987), 159-172. [1464, A- two-dimensional. [901.2,ACG-CDCTDPA-SIAMJC-89] OAGC-JA-87] 193 M. J. Atallah and M. T. Goodrich. Efficient parallel 206 L. J. Aupperle, H. E. Conn, J. M. Keil and J. solutions to some geometric problems. J. Parallel Distrib. O’Rourke. Covering orthogonal polygons with squares. In Comput.3(1986),492-507. Keywords: parallelcomputation, Proc.26thAllertonConf.Commun.ControlComput.(October convex hull, proximity, divide-and-conquer, points, two- 1988), 97-106. Keywords: covering, decomposition, dimensional. [882,AG-EPSSGP-JPDC-86] polygons, NP-completeness, image processing, graph theory, squares,medialaxis. [2431,ACKO-COPS-26ACCCC-88] 194 M. J. Atallah and M. T. Goodrich. Efficient plane sweepinginparallel. InProc.2ndAnnu.ACMSympos.Com- 207 L.J.AupperleandJ.M.Keil. Polynomialalgorithms put. Geom. (1986), 216-225. Keywords: parallel computa- for restricted Euclidean p-centre problems. Discrete Appl. tion, decomposition, range search, point location, triangula- Math. 23 (1989), 25-31. Keywords: lines, cluster analysis, tion, visibility, domination, points, lines, two-dimensional. dynamic programming, circles, optimization, operations [820,AG-EPSP-2SCG-86] research. [2357,AK-PAREPCP-DAM-89] 195 M.J.AtallahandM.T.Goodrich. Parallelalgorithms 208 F.Aurenhammer. Acriterionfortheaffineequalityof forsomefunctionsoftwoconvexpolygons. InProc.24thAll- cellcomplexesinRd andconvexpolyhedrainRd+1. Discrete ertonConf.Commun.ControlComput.(1986),758-767. Key- Comput. Geom. 2 (1987), 49-64. Keywords: discrete words: parallelcomputation,convexhull,distance,polygons, geometry,cell complexes, polyhedra,convex, d-dimensional, convex, two-dimensional. [887.1, AG-PASFTCP- spheres. [200,A-CAECCRSDCPRSD1-DCG-87] 24ACCCC-86] 209 F. Aurenhammer. A new duality result concerning 196 M.J.AtallahandM.T.Goodrich. Parallelalgorithms Voronoi diagrams. In Proc. 13th Internat. Colloq. Automat. forsomefunctionsoftwoconvexpolygons. Algorithmica3:4 Lang. Program., Lecture Notes in Computer Science 226, (1988), 535-548. Keywords: parallel computation, convex Springer-Verlag (1986), 21-30. Keywords: design of algo- hull, distance, polygons, convex, two-dimensional. [887.2, rithms, discrete geometry, duality, Voronoi diagrams, convex AG-PASFTCP-A-88] hull,worst-caseanalysis. [201.1,A-NDRCVD-13ICALP-86] 197 M. J. Atallah and S. R. Kosaraju. A generalized dic- 210 F. Aurenhammer. A new duality result concerning tionarymachineforVLSI. IEEETrans.Comput.C-34(1985), Voronoi diagrams. Discrete Comput. Geom. 5 (1990), 243- 151-155. [881,AK-GDMV-IEEETC-85] 254. Keywords: design of algorithms, discrete geometry, duality, Voronoi diagrams, convex hull, worst-case analysis. 198 M. J. Atallah and S. R. Kosaraju. An efficient algo- [201.2,A-NDRCVD-DCG-90] rithm for maxdominance, with applications. Report CSD- TR-641, Dept. Comput. Sci., Purdue Univ., West Lafayette, 211 F. Aurenhammer. A relationship between Gale IN(1987). [1775,AK-EAMA-PU-87] transformsandVoronoidiagrams. Report247,Inst.Informa- tionsverarb.,Tech.Univ.Graz,Graz,Austria(1988). [1988.1, 199 M.J.AtallahandS.R.Kosaraju. Anefficientparallel A-RBGTVD-TUG-88] algorithmfortherowminimaofatotallymonotonematrix. In Proc. 2nd ACM-SIAM Sympos. Discrete Algorithms (1991), 212 F. Aurenhammer. A relationship between Gale 394-403. Other: O(logn) time, O(n) processors, EREW- transforms and Voronoi diagrams. Discrete Appl. Math. 28 PRAMmodel. [2561,AK-EPARMTMM-2SODA-91] (1991),83-91. [1988.2,A-RBGTVD-DAM-91] 200 M. J. Atallah and S. R. Kosaraju. Efficient solutions 213 F.Aurenhammer. Efficient computationof low-order to some maxdominance problems. In Proc. 21st Ann. Conf. Voronoi diagrams via convex hulls. Report 216, Inst. Infor- Inform. Sci. Systems (1987), ??-??. [888, AK-ESSMP- mationsverarb., Tech. Univ. Graz, Graz, Austria (1985). 21ACISS-87] [1030,A-ECLOVDCH-TUG-85] 201 M. J. Atallah and S. R. Kosaraju. Minimizing robot 214 F. Aurenhammer. Gewichtete Voronoi Diagramme: arm travel. Technical Report ??, Dept. Comput. Sci., Purdue Geometrische Deutung und Konstruktions-Algorithmen. Univ.,WestLafayette,IN(19??). [903,AK-MRAT-PU-??] Report B53, Inst. Informationsverarb., Tech. Univ. Graz, Graz, Austria (1984). Keywords: doctoral thesis, discrete 202 M. J. Atallah and J.-J. Tsay. On the parallel- geometry, design of algorithms, geometric transformations, decomposability of geometric problems. In Proc. 5th Annu. Voronoi diagrams, weighted, d-dimensional. [1027, A- ACM Sympos. Comput. Geom. (1989), 104-113. [2138, AT- GVDGDKA-TUG-84] PDGP-5SCG-89] 215 F. Aurenhammer. Improved algorithms for discs and M.J.Atallah. Seealso1209[2813]. ballsusingpowerdiagrams. J.Algorithms9(1988),151-161. 203 A. Athavale and D. M. Mount. Order type and iso- Keywords: designofalgorithms,computergraphics,robotics, myphism based on enclosing circles. Report ??, Dept. Com- intersection, volume, Voronoi diagrams, disks, balls. [1029, put. Sci., Univ. Maryland College Park, College Park, MD A-IADBPD-JA-88] (1985). [1575,AM-OTIBEC-UMCP-85] 216 F. Aurenhammer. Jordan sorting via convex hulls of 204 P.Atherton,K.WeilerandD.P.Greenberg. Polygon certain non-simple polygons. In Proc. 3rd Annu. ACM Sym- shadow generation. In Proc. SIGGRAPH ’78, Comput. pos. Comput. Geom. (1987), 21-29. Keywords: design of Graph. 12:3 (1978), 275-281. [20, AWG-PSG- algorithms, sorting, convex hull, non-simple polygons, trees, SIGGRAPH78-78] worst-case analysis. Other: not presented. [204, A- JSCHCNSP-3SCG-87] P.Atherton. Seealso2777[1642]. 217 F. Aurenhammer. On the generality of power 205 M. D. Atkinson. An optimal algorithm for geometri- diagrams. ReportF126,Inst.Informationsverarb.,Tech.Univ. March4,1992 -- -- ComputationalGeometryBibliography 9 Graz, Graz, Austria (1983). Keywords: discrete geometry, 229 F. Aurenhammer and H. Imai. Geometric relations cell complexes, polyhedra, convex, d-dimensional, spheres. amongVoronoidiagrams. Geom.Dedicata27(1988),65-75. [1026,A-GPD-TUG-83] Keywords: design of algorithms, discrete geometry, Voronoi diagrams,distance,weighted. [202.2,AI-GRVD-GD-88] 218 F. Aurenhammer. On-line sorting of twisted sequencesinlineartime. Report??,Inst.Informationsverarb., 230 F. Aurenhammerand O. Schwarzkopf. A simple on- Tech.Univ.Graz,Graz,Austria(1987). Keywords: designof line randomized incremental algorithm for computing higher algorithms, sorting, convex hull, arrangements, incrementa- order Voronoi diagrams. In Proc. 7th Annu. ACM Sympos. tion, worst-case analysis, lower bounds. [203, A-LSTSLT- Comput. Geom. (1991), 142-151. Keywords: Voronoi TUG-87] diagrams, geometric transforms. [2583, AS-SLRIACHOVD- 7SCG-91] 219 F. Aurenhammer. Power diagrams: properties, algo- rithms and applications. SIAM J. Comput. 16 (1987), 78-96. 231 G. Ausiello,G. F.Italiano, A. M. Spaccamela and U. Keywords: discretegeometry,designofalgorithms,geometric Nanni. Incremental algorithms for minimal length paths. In transformations, duality, Voronoi diagrams, convex hull, Proc. 1st ACM-SIAM Sympos. Discrete Algorithms (1990), arrangements, d-dimensional, distance, weighted. [673, A- 12-21. [2309,AISN-IAMLP-1SODA-90] PDPAA-SIAMJC-87] 232 Z.AviadandE.Shamir. Adirectdynamicsolutionto 220 F. Aurenhammer. Recognizing polytopical cell com- range search and related problems for product regions. In plexes and constructing projection polyhedra. J. Symbolic Proc.22ndAnnu.IEEESympos.Found.Comput.Sci.(1982), Comput.3(1987),249-255. Keywords: designofalgorithms, 123-126. Keywords: orthogonal range queries, integer coor- cell complexes, Voronoi diagrams, image processing, pattern dinates, multidimensional search. [21, AS-DDSRSRPPR- recognition. [1028,A-RPCCCPP-JSC-87] 22FOCS-82] 221 F. Aurenhammer. The one-dimensional weighted 233 D. Avis. A survey of heuristics for the weighted Voronoi diagram. Inform. Process. Lett. ?? (1986), 119-123. matchingproblem. Networks13(1983),475-493. Keywords: Keywords: design of algorithms, divide-and-conquer, plane- heuristics, worst-case analysis, average-case analysis. [992, sweep, worst-case analysis, Voronoi diagrams, weighted. A-SHWMP-N-83] [1025,A-DWVD-IPL-86] 234 D.Avis. Commentsonalowerboundforconvexhull 222 F.Aurenhammer. UsingGaletransformsincomputa- determination. Inform. Process. Lett. 11 (1980), 126. Key- tionalgeometry. Report248,Inst.Informationsverarb.,Tech. words: convexhull,lowerbounds,lineardecisiontrees. [23, Univ. Graz, Graz, Austria (1988). [1973.1, A-GTCG-TUG- A-CLBCHD-IPL-80] 88] 235 D. Avis. Diameter partitioning. Discrete Comput. 223 F.Aurenhammer. UsingGaletransformsincomputa- Geom.1(1986),265-276. Keywords: planarpointsets,parti- tionalgeometry. InComputationalGeometryanditsApplica- tion,diameter. [762,A-DP-DCG-86] tions, Lecture Notes in Computer Science 333, Springer- 236 D. Avis. Lower bounds for geometric problems. In Verlag(1988),202-216. [1973.2,A-GTCG-CGA-88] Proc. 18th Allerton Conf. Commun. Control Comput. (1980), 224 F. Aurenhammer. Voronoi diagrams: a survey of a 35-40. Keywords: lower bounds, linear decision trees, qua- fundamental geometric data structure. Report B-90-09, draticdecisiontrees. [24,A-LBGP-18ACCCC-80] Fachber. Math., Free Univ. Berlin, Berlin (1990). [2467.2, 237 D. Avis. Non-partitionable point sets. Inform. Pro- A-VDSFGDS-FUB-90] cess.Lett.19(1984),125-129. Keywords: discretegeometry, 225 F. Aurenhammer. Voronoi diagrams: a survey of a decomposition,rangesearch. [899,A-NPPS-IPL-84] fundamentalgeometricdatastructure. ACMComput.Surv.23 238 D.Avis. Onthecomplexityoffindingtheconvexhull (1991), 345-405. Keywords: survey paper, Voronoi ofasetofpoints. DiscreteAppl.Math.4(1982),81-86. Key- diagrams, Delaunay triangulations, arrangements, hyper- words: convexhull,lowerbounds,lineardecisiontrees. [22, planes, plane sweep, divide-and-conquer, parallel computa- A-CFCHSP-DAM-82] tion, minimum spanning trees, cluster analysis, motion plan- ning. [2467.3,A-VDSFGDS-ACMCS-91] 239 D.Avis. Onthepartitionabilityofpointsetsinspace. In Proc. 1st Annu. ACM Sympos. Comput. Geom. (1985), 226 F. Aurenhammer. Voronoi diagrams, a survey. 116-120. Keywords: point sets, partition, half spaces. [754, Report 263, Inst. Inform. Process., Tech. Univ. Graz, Graz, A-PPSS-1SCG-85] Austria(1988). [2467.1,A-VDS-TUG-88] 240 D.Avis. Spacepartitioninganditsapplicationtogen- 227 F. Aurenhammer and H. Edelsbrunner. An optimal eralized retrieval problems. In Proc. Internat. Conf. Found. algorithm for constructing the weighted Voronoi diagram in DataOrganization,Kyoto,Japan(1985),154-162. Keywords: the plane. Pattern Recogn. 17 (1984), 251-257. Keywords: point sets, partition, half spaces. [753, A-SPAGRP-ICFDO- combinatorial geometry, design of algorithms, construction, 85] incrementation, geometric transformations, worst-case analysis, Voronoi diagrams, two-dimensional, three- 241 D.Avis. Thenumberoffurthestneighborsofafinite dimensional,weighted. [742,AE-OACWVDP-PR-84] planar set. Amer. Math. Monthly 91 (1984), 417-420. Key- words: combinatorial geometry, proximity. [2503, A- 228 F. Aurenhammer and H. Imai. Geometric relations NFNFPS-AMM-84] among Voronoi diagrams. In Proc. 4th Sympos. Theoret. AspectsComput.Sci.,LectureNotesinComputerScience247, 242 D.Avis. WorstcaseboundsfortheEuclideanmatch- Springer-Verlag (1987), ??-??. Keywords: design of algo- ing problem. Comput. Math. Appl. 7 (1981), 251-257. Key- rithms, discrete geometry, Voronoi diagrams, distance, words: heuristics, worst-case analysis. [25, A-WCBEMP- weighted. [202.1,AI-GRVD-4STACS-87] CMA-81] March4,1992 -- -- 10 ComputationalGeometryBibliography 243 D.AvisandB.K.Bhattacharya. Algorithmsforcom- [2758,ARW-LBLS-IPL-89] putingd-dimensionalVoronoidiagramsandtheirduals. InF. 257 D. Avis and G. T. Toussaint. An efficient algorithm P. Preparata, ed., Adv. Comput. Res., 1, JAI Press (1983), for decomposing a polygon into star-shaped polygons. Pat- 159-180. Keywords: Voronoi diagrams, d-dimensional, ternRecogn.13(1981),395-398. Keywords: decomposition, linearprogramming. [1183,AB-ACDDVDD-ACR-83] polygons,star-shaped,coloring. [27,AT-EADPSSP-PR-81] 244 D.Avis,B.K.BhattacharyaandH.Imai. Computing 258 D. Avis and G. T. Toussaint. An optimal algorithm the volume of the union of spheres. Technical Report SOCS for determining the visibility of a polygon from an edge. 87.3, McGill Univ., Montreal, PQ (1987). Keywords: IEEE Trans. Comput. C-30 (1981), 910-1014. Keywords: volume, spheres, Voronoi diagrams. [829, ABI-CVUS- combinatorial geometry, design of algorithms, construction, MGU-87] incrementation, geometric transformations, worst-case 245 D.AvisandM.Deza. L embeddability, complexity, analysis, Voronoi diagrams, two-dimensional, three- 1 and multicommodity flows. In Proc. 1st Canad. Conf. Com- dimensional,weighted. [26,AT-OADVPE-IEEETC-81] put.Geom.(1989),30. [2661,AD-LS1ECMF-1CCCG-89] 259 D.Avis,G.T.ToussaintandB.K. Bhattacharya. On 246 D. Avis and M. Doskas. Algorithms for high dimen- the multimodality of distances in convex polygons. Comput. sional stabbing problems. Technical Report SOCS 87.2, Math. Appl. 8 (1982), 153-156. Keywords: discrete McGillUniv.,Montreal,PQ(1987). Keywords: transversals, geometry, diameter, planar point sets. [28, ATB-MDCP- hyperplanes, stabbing, polyhedra, linear programming. [825, CMA-82] AD-AHDSP-MGU-87] 260 D.AvisandR.Wenger. Algorithmsforlinetransver- 247 D.AvisandH.ElGindy. Acombinatorialapproachto sals in space. In Proc. 3rd Annu. ACM Sympos. Comput. polygonsimilarity. IEEE Trans.Inform.TheoryIT-2 (1983), Geom.(1987),300-307. [1267.1,AW-ALTS-3SCG-87] 148-150. Keywords: polygons, similarity, pattern matching, 261 D. Avis and R. Wenger. Polyhedral line transversals visibilitygraphs. [1184,AE-CAPS-IEEETIT-83] in space. Discrete Comput. Geom. 3 (1988), 257-265. 248 D. Avis and H. ElGindy. Triangulating simplicial [1267.2,AW-PLTS-DCG-88] point sets in space. In Proc. 2nd Annu. ACM Sympos. Com- D. Avis. See also 992[1628], 993[1629], 1817[409], put. Geom. (1986), 133-141. Keywords: triangulation, 2697[613]. decomposition, three-dimensional, d-dimensional, point sets. [811,AE-TSPSS-2SCG-86] 262 F. Avnaim and J. D. Boissonnat. Practical exact motionplanningofaclassofrobotswiththreedegreesoffree- 249 D. Avis, H. ElGindy and R. Seidel. Simple on-line dom. In Proc. 1st Canad. Conf. Comput. Geom. (1989), 19. algorithms for convex polygons. In G. T. Toussaint, ed., [2650,AB-PEMPCRTDF-1CCCG-89] ComputationalGeometry,North-Holland,Amsterdam(1985), 23-42. Keywords: convex hull, on-line, planar point sets, 263 F. Avnaim and J.-D. Boissonnat. Simultaneous con- intersection,polygons. [1185,AES-SLACP-CG-85] tainmentof severalpolygons. In Proc. 3rdAnnu.ACMSym- pos. Comput. Geom. (1987), 242-250. [1229, AB-SCSP- 250 D. Avis, P. Erdo"s and J. Pach. Distinct distances 3SCG-87] determinedbysubsetsofapointsetinspace. Comput.Geom. TheoryAppl.1(1991),1-11. [2834,AEP-DDDSPSS-CGTA- 264 D. Ayala, P. Brunet, R. Juan and I. Navazo. Object 91] representationbymeansofnominaldivisionquadtrees. ACM Trans. Graph. 4:1 (1985), 41-59. [1455, ABJN-ORMNDQ- 251 D. Avis,P. Erdo"sand J. Pach. Repeated distances in ACMTG-85] the space. Graphs Combin. 4 (1988), 207-217. Keywords: combinatorialgeometry,proximity. [2504,AEP-RDS-GC-88] E.Backer. Seealso1297[1828]. 252 D.AvisandK.Fukuda. Apivotingalgorithmforcon- 265 N.BadlerandR.Bajcsy. 3-drepresentationforcom- vexhullsandvertexenumerationofarrangementsandpolyhe- puter graphics and computer vision. Comput. Graph. Image dra. InProc.7thAnnu.ACMSympos.Comput.Geom.(1991), Process.12(1978),153-160. [29,BB-3DRCGCV-CGIP-78] 98-104. Keywords: polytopes, linear programming. [2578, N.Badler. Seealso2240[1713]. AF-PACHVEAP-7SCG-91] N.I.Badler. Seealso2095[448],2096[1115]. 253 D.Avis,T.GumandG.Toussaint. Visibilitybetween two edges of a simple polygon. Visual Comput. ?? (19??), P.O.Baehmann. Seealso2490[1726]. ??-??. Keywords: polygons, edge visibility. Other: to R.Baeza-Yates. Seealso2262[2081]. appear. [1577,AGT-VBTESP-VC-??] 266 F. Bagemihl. On indecomposable polyhedra. Report 254 D. Avis and M. E. Houle. Computational aspects of ??,Univ.Rochester(19??). [1932,B-IP-UR-??] Helly’s theorem and its relatives. In Proc. 3rd Canad. Conf. Comput. Geom. (1991), 11-14. [2683, AH-CAHSTR- ?Baillieul. Seealso848[2525]. 3CCCG-91] 267 C. Bajaj. An efficient parallel solution for Euclidean 255 D. Avis and D. Rappaport. Computing the largest shortest paths in three dimensions. In Proc. IEEE Internat. empty convex subset of a set of points. In Proc. 1st Annu. Conf. Robotics Automat., San Francisco, CA (1986), ??-??. ACM Sympos. Comput. Geom. (1985), 161-167. Keywords: Keywords: motion planning, elementary geometry, parallel planar point sets, convex subsets, discrete geometry. [779, computation, geodesic distance, numerical analysis, CAD, AR-CLECSSP-1SCG-85] robotics. [1033,B-EPSESPTD-ICRA-86] 256 D.Avis,J.-M.RobertandR.Wenger. Lowerbounds 268 C. Bajaj. Geometric optimization and computational for line stabbing. Inform. Process. Lett. 33 (1989), 59-62. complexity. Report TR 84-629, Dept. Comput. Sci., Cornell March4,1992