{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:29Z","timestamp":1725664529655},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_65","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:52:06Z","timestamp":1330278726000},"page":"228-238","source":"Crossref","is-referenced-by-count":0,"title":["A linear-time construction of the relative neighborhood graph within a histogram"],"prefix":"10.1007","author":[{"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[]},{"given":"Asish","family":"Mukhopadhyay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, L.J. Guibas, J. Saxe, and P.W. Shor, A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon. Discrete and Computational Geometry 4, 1987.","DOI":"10.1145\/28395.28400"},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0218195992000020","volume":"2","author":"P.K. Agarwal","year":"1992","unstructured":"P.K. Agarwal and J. Matousek, Relative Neighborhood Graphs in Three Dimensions, Computational Geometry: Theory and Applications 2(1), pp. 1\u201314 (1992).","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"F. Aurenhammer, Voronoi Diagrams \u2014 A Survey of a Fundamental Geometric Data Structure, ACM Computing Surveys, Vol. 23, No. 3, September 1991, pp.345\u2013406.","journal-title":"ACM Computing Surveys"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01553881","volume":"4","author":"L. P. Chew","year":"1989","unstructured":"L. P. Chew, Constrained Delaunay Triangulations, Algorithmica 4 (1989), pp. 97\u2013108.","journal-title":"Algorithmica"},{"issue":"2","key":"20_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A. Fournier","year":"1984","unstructured":"A. Fournier and D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics 3(2), pp. 153\u2013174, 1984.","journal-title":"ACM Transactions on Graphics"},{"key":"20_CR6","doi-asserted-by":"crossref","first-page":"259","DOI":"10.2307\/2412323","volume":"18","author":"K. R. Gabriel","year":"1969","unstructured":"K. R. Gabriel and R. R. Sokal, A New Statistical Approach to Geographic Variation Analysis, Systematic Zoology 18 (1969), pp. 259\u2013278.","journal-title":"Systematic Zoology"},{"issue":"4","key":"20_CR7","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M.R. Garey","year":"1978","unstructured":"M.R. Garey, D.S. Johnson, F.P. Preparata and R.E. Tarjan, Triangulating a simple polygon, IPL 7(4), pp. 175\u2013179, 1978.","journal-title":"IPL"},{"key":"20_CR8","unstructured":"E. Jennings and A. Lingas, Relationships between Constrained Geometric Structures, Proc. ISAAC'92, Nagoya, LNCS 650, pp. 165\u2013176, Springer Verlag."},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"J.W. Jaromczyk and M. Kowaluk, A note on relative neighborhood graphs, Proc. 3rd ACM Symp. on Computational Geometry, pp. 233\u2013241 (1987).","DOI":"10.1145\/41958.41983"},{"key":"20_CR10","unstructured":"J.W. Jaromczyk and M. Kowaluk and F.F. Yao, An Optimal Algorithm for Constructing \u03b2-skeletons in Lp metric, to appear in SIAM J. Computing."},{"issue":"9","key":"20_CR11","doi-asserted-by":"publisher","first-page":"1502","DOI":"10.1109\/5.163414","volume":"80","author":"J. W. Jaromczyk","year":"1992","unstructured":"J. W. Jaromczyk and G. T. Toussaint, Relative Neighborhood Graphs and Their Relatives, Proceedings of the IEEE 80(9), pp.1502\u20131516 (1992).","journal-title":"Proceedings of the IEEE"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"R. Klein and A. Lingas, Manhattonian Proximity in a Simple Polygon, Proc. 8th ACM Symposium on Computational Geometry, Berlin, 1992, pp. 312\u2013319. To appear in Int. J. Comput. Geom. & Applications.","DOI":"10.1145\/142675.142738"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"R. Klein and A. Lingas, A Linear-time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon, Proc. ACM Symposium on Computational Geometry, San Diego, 1993.","DOI":"10.1145\/160985.161008"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"R. Klein and A. Lingas, Fast Skeleton Construction, manuscript 1994.","DOI":"10.1007\/3-540-60313-1_172"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"D.G. Kirkpatrick and J.D. Radke, A Framework for Computational Morphology, in Computational Geometry, edited by G. Toussaint, pp. 217\u2013248, North-Holland, 1985.","DOI":"10.1016\/B978-0-444-87806-9.50013-X"},{"key":"20_CR16","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0925-7721(94)90018-3","volume":"4","author":"A. Lingas","year":"1994","unstructured":"A. Lingas, A linear-time construction of the relative neighborhood graph from the Delaunay triangulation, Computational Geometry: Theory and Applications 4, pp. 199\u2013208 (1994).","journal-title":"Computational Geometry: Theory and Applications"},{"key":"20_CR17","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02187695","volume":"1","author":"D. T. Lee","year":"1986","unstructured":"D. T. Lee and A. K. Lin, Generalized Delaunay Triangulation for Planar Graphs, Discrete and Computational Geometry, 1 (1986), pp. 201\u2013217.","journal-title":"Discrete and Computational Geometry"},{"issue":"3","key":"20_CR18","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF00977785","volume":"9","author":"D.T. Lee","year":"1980","unstructured":"D.T. Lee and B. Schachter, Two algorithms for constructing Delaunay triangulations, Int. J. Comput. and Info. Sci. 9(3), pp. 219\u2013242 (1980).","journal-title":"Int. J. Comput. and Info. Sci."},{"key":"20_CR19","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1111\/j.1538-4632.1980.tb00031.x","volume":"12","author":"D.W. Matula","year":"1980","unstructured":"D.W. Matula and R.R. Sokal, Properties of Gabriel graphs relevant to geographic variation search and the clustering of points in the plane, Geogr. Analysis 12, pp. 205\u2013222 (1980).","journal-title":"Geogr. Analysis"},{"key":"20_CR20","volume-title":"Texts and Monographs in Theoretical Computer Science","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Texts and Monographs in Theoretical Computer Science, Springer Verlag, New York, 1985."},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0031-3203(80)90066-7","volume":"12","author":"G.T. Toussaint","year":"1980","unstructured":"G.T. Toussaint, The relative neighbourhood graph of a finite planar set, Pattern Recognition 12, pp. 261\u2013268 (1980).","journal-title":"Pattern Recognition"},{"key":"20_CR22","first-page":"178","volume-title":"Rep. 260","author":"R. Seidel","year":"1988","unstructured":"R. Seidel, Constrained Delaunay Triangulations and Voronoi Diagrams with Obstacles, In Rep. 260, IIG-TU, Graz, Australia, 1988, pp. 178\u2013191."},{"key":"20_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0031-3203(91)90064-C","volume":"24","author":"T.H. Su","year":"1991","unstructured":"T.H. Su and R.C. Chang, Computing the constrained relative neighborhood graphs and constrained Gabriel graphs in Euclidean plane, Pattern Recognition 24, pp. 221\u2013230 (1991).","journal-title":"Pattern Recognition"},{"key":"20_CR24","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/2402.322386","volume":"30","author":"K.J. Supowit","year":"1983","unstructured":"K.J. Supowit, The relative neighborhood graph with an application to minimum spanning trees, J. Assoc. Comput. Mach. 30, pp. 428\u2013448 (1983).","journal-title":"J. Assoc. Comput. Mach."},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"C. A. Wang and L. Schubert, An Optimal Algorithm for Constructing the Delaunay Triangulation of a Set of Line Segments, Proc. 3 rd Annual Symposium on Computational Geometry, June 8\u201310, 1987, Waterloo, Ontario, Canada, pp. 223\u2013232.","DOI":"10.1145\/41958.41982"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:56:10Z","timestamp":1605646570000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}