{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:27:33Z","timestamp":1751282853101},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,4,1]],"date-time":"1996-04-01T00:00:00Z","timestamp":828316800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1996,4]]},"DOI":"10.1007\/bf02712872","type":"journal-article","created":{"date-parts":[[2007,10,3]],"date-time":"2007-10-03T05:58:49Z","timestamp":1191391129000},"page":"339-359","source":"Crossref","is-referenced-by-count":17,"title":["Triangulations intersect nicely"],"prefix":"10.1007","volume":"16","author":[{"given":"O.","family":"Aichholzer","sequence":"first","affiliation":[]},{"given":"F.","family":"Aurenhammer","sequence":"additional","affiliation":[]},{"given":"Siu-Wing","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"N.","family":"Katoh","sequence":"additional","affiliation":[]},{"given":"G.","family":"Rote","sequence":"additional","affiliation":[]},{"given":"M.","family":"Taschwer","sequence":"additional","affiliation":[]},{"given":"Yin-Feng","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02712872_CR1","doi-asserted-by":"crossref","unstructured":"[AART] O. Aichholzer, F. Aurenhammer, G. Rote, and M. Taschwer, Triangulations intersect nicely,Proc. 11th Ann. Symp. on Computational Geometry, Vancouver, British Columbia, June 1995, pp. 220\u2013229.","DOI":"10.1145\/220279.220303"},{"key":"BF02712872_CR2","unstructured":"[AARX] O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu, New greedy triangulation algorithms, in preparation."},{"key":"BF02712872_CR3","volume-title":"Graph Theory. An Introductory Course","author":"B. Bollob\u00e1s","year":"1979","unstructured":"[B1] B. Bollob\u00e1s,Graph Theory. An Introductory Course, Springer-Verlag, Berlin, 1979."},{"key":"BF02712872_CR4","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1017\/S000497270004140X","volume":"1","author":"R. A. Brualdi","year":"1969","unstructured":"[B2] R. A. Brualdi, Comments on bases in dependence structures,Bull. Austral. Math. Soc. 1 (1969), 161\u2013167.","journal-title":"Bull. Austral. Math. Soc."},{"key":"BF02712872_CR5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0012-365X(73)90064-2","volume":"6","author":"T. H. Brylawski","year":"1973","unstructured":"[B3] T. H. Brylawski, Some properties of basic families of subsets,Discrete Math. 6 (1973), 333\u2013341.","journal-title":"Discrete Math."},{"key":"BF02712872_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BFb0030818","volume-title":"Computing and Combinatorics","author":"S.-W. Cheng","year":"1995","unstructured":"[CX1] S.-W. Cheng and Y.-F. Xu, Constrained independence system and triangulations of planar point sets, in: D.-Z. Du and Ming Li, (eds.),Computing and Combinatorics, Proc. First Ann. Internat. Conf., COCOON'95, Xi'an, China, August 1995. Lecture Notes in Computer Science, Vol. 959, Springer-Verlag, Berlin, 1995, pp. 41\u201350."},{"key":"BF02712872_CR7","doi-asserted-by":"crossref","unstructured":"[CX2] S.-W. Cheng and Y.-F. Xu, Approaching the largest \u03b2-skeleton within a minimum-weight triangulation,Proc. 12th Ann. Symp. on Computational Geometry, Philadelphia, PA, 1996, pp. 196\u2013203.","DOI":"10.1145\/237218.237360"},{"key":"BF02712872_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","volume-title":"Proc. Internat. Symp. on Optimal Algorithms","author":"G. Das","year":"1989","unstructured":"[DJ] G. Das and D. Joseph, Which triangulations approximate the complete graph,Proc. Internat. Symp. on Optimal Algorithms, Lecture Notes in Computer Science, Vol. 401, Springer-Verlag, Berlin, 1989, pp. 168\u2013192."},{"key":"BF02712872_CR9","doi-asserted-by":"crossref","unstructured":"[DDMW] M. Dickerson, R. L. Drysdale, S. McElfresh, and E. Welzl, Fast greedy triangulation algorithms,Proc. 10th Ann. Symp. on Computational Geometry, 1994, pp. 211\u2013220.","DOI":"10.1145\/177424.177649"},{"key":"BF02712872_CR10","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1142\/S0218195992000147","volume":"3","author":"M. Dickerson","year":"1992","unstructured":"[DDS] M. Dickerson, R. L. Drysdale, and J.-R. Sack, Simple algorithms for enumerating interpoint distances and findingk nearest neighbors,Internat. J. Comput. Geom. Appl. 3 (1992), 221\u2013239.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02712872_CR11","doi-asserted-by":"crossref","unstructured":"[DM] M. T. Dickerson and M. H. Montague, A. (usually?) connected subgraph of the minimum weight triangulation,Proc. 12th Ann. Symp. on Computational Geometry, Philadelphia, PA, 1996, pp. 204\u2013213.","DOI":"10.1145\/237218.237364"},{"key":"BF02712872_CR12","unstructured":"[DRA] R. L. Drysdale, G. Rote, and O. Aichholzer, A simple linear time greedy triangulation algorithm for uniformly distributed points, Report IIG-408, Institutes for Information Processing, Technische Universit\u00e4t Graz, February 1995, 16 pages."},{"key":"BF02712872_CR13","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"[GJ] M. Garey and D. Johnson,Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979."},{"key":"BF02712872_CR14","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0020-0190(89)90122-1","volume":"31","author":"S. Goldman","year":"1989","unstructured":"[G] S. Goldman, A space efficient greedy triangulation algorithm,Inform. Process. Lett. 31 (1989), 191\u2013196.","journal-title":"Inform. Process. Lett."},{"key":"BF02712872_CR15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"[HK] J. E. Hopcroft and R. Karp, Ann 5\/2 algorithm for maximum matchings in bipartite graphs,SIAM J. Comput. 2 (1973), 225\u2013231.","journal-title":"SIAM J. Comput."},{"key":"BF02712872_CR16","doi-asserted-by":"crossref","unstructured":"[HNU] F. Hurtado, M. Noy, and J. Urrutia, Flipping edges in triangulations,Proc. 12th Ann. Symp. on Computational Geometry, Philadelphia, PA, 1996, pp. 214\u2013223.","DOI":"10.1145\/237218.237367"},{"key":"BF02712872_CR17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0925-7721(94)90014-0","volume":"4","author":"M. Keil","year":"1994","unstructured":"[K] M. Keil, Computing a subgraph of the minimum weight triangulation,Comput. Geom. Theory Appl. 4 (1994), 13\u201326.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02712872_CR18","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"[L] E. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, 1976."},{"key":"BF02712872_CR19","series-title":"Tech. Report LU-CS-TR:94-136","volume-title":"The greedy triangulation can be computed from the Delaunay in linear time","author":"C. Levcopoulos","year":"1994","unstructured":"[LK1] C. Levcopoulos and D. Krznaric, The greedy triangulation can be computed from the Delaunay in linear time, Tech. Report LU-CS-TR:94-136, Dept. of Computer Science and Numer. Analysis, Lund University, Lund, Sweden, 1994."},{"key":"BF02712872_CR20","unstructured":"[LK2] C. Levcopoulos and D. Krznaric, Quasi-greedy triangulations approximating the minimum weight triangulation,Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 1996, pp. 392\u2013401."},{"key":"BF02712872_CR21","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1987","unstructured":"[T] R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1987."},{"key":"BF02712872_CR22","volume-title":"Minimum weight triangulation problem of a planar point set","author":"Y.-F. Xu","year":"1992","unstructured":"[X] Y.-F. Xu, Minimum weight triangulation problem of a planar point set, Ph.D. Thesis, Institute of Applied Mathematics, Academia Sinica, Beijing, 1992."},{"key":"BF02712872_CR23","series-title":"Lecture Notes in Computer Science","first-page":"423","volume-title":"A chain decomposition algorithm for the proof of a property on minimum weight triangulations","author":"B.-T. Yang","year":"1994","unstructured":"[YXY] B.-T. Yang, Y.-F. Xu, and Z.-Y. You, A chain decomposition algorithm for the proof of a property on minimum weight triangulations,Proc. 5th Internat. Symp. on Algorithms and Computation (ISAAC'94), Lecture Notes in Computer Science, Vol. 834, Springer-Verlag, Berlin, 1994, pp. 423\u2013427."},{"key":"BF02712872_CR24","first-page":"352","volume-title":"Display and Analysis of Spatial Data","author":"P. Yoeli","year":"1975","unstructured":"[Y] P. Yoeli, Compilation of data for computer-assisted relief cartography, in: J. C. Davis and M. J. McCullagh (eds.),Display and Analysis of Spatial Data, Wiley, New York, 1975, pp. 352\u2013367."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02712872.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02712872\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02712872","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T01:01:23Z","timestamp":1558227683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02712872"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["BF02712872"],"URL":"https:\/\/doi.org\/10.1007\/bf02712872","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}