{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:51:47Z","timestamp":1772502707654,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1007\/bf02574385","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:11:43Z","timestamp":1174565503000},"page":"347-365","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Can visibility graphs Be represented compactly?"],"prefix":"10.1007","volume":"12","author":[{"given":"P. K.","family":"Agarwal","sequence":"first","affiliation":[]},{"given":"N.","family":"Alon","sequence":"additional","affiliation":[]},{"given":"B.","family":"Aronov","sequence":"additional","affiliation":[]},{"given":"S.","family":"Suri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1994,9,1]]},"reference":[{"key":"BF02574385_CR1","doi-asserted-by":"crossref","unstructured":"P. Agarwal, M. Sharir, and S. Toledo, Applications of parametric searching in geometric optimization,J. Algorithms (1993), to appear.","DOI":"10.1006\/jagm.1994.1038"},{"key":"BF02574385_CR2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0020-0190(90)90167-V","volume":"35","author":"A. Aggarwal","year":"1990","unstructured":"A. Aggarwal and S. Suri, The biggest diagonal in a simple polygon,Inform. Process. Lett. 35 (1990), 13\u201318.","journal-title":"Inform. Process. Lett."},{"key":"BF02574385_CR3","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1991","unstructured":"N. Alon and J. H. Spencer,The Probabilistic Method, Wiley, New York, 1991."},{"key":"BF02574385_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle, A polygon cutting theorem,Proc. 23rd IEEE Symp. on Foundations of Computer Science, 1982, pp. 339\u2013349.","DOI":"10.1109\/SFCS.1982.58"},{"key":"BF02574385_CR5","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle, Lower bounds on the complexity of polytope range searching,J. Amer. Math. Soc.,2 (1989), 637\u2013666.","journal-title":"J. Amer. Math. Soc."},{"key":"BF02574385_CR6","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1145\/79147.79149","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle, Lower bounds for the orthogonal range searching: II. The arithmetic model,J Assoc. Comput. Mach. 37 (1990), 439\u2013463.","journal-title":"J Assoc. Comput. Mach."},{"key":"BF02574385_CR7","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B. Chazelle","year":"1994","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Algorithms for bichromatic line segment problems and polyhedral terrains.Algorithmica 11 (1994), 116\u2013132.","journal-title":"Algorithmica"},{"key":"BF02574385_CR8","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Discrete Comput. Geom. 4 (1989), 551\u2013589.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574385_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1142\/S0218195991000049","volume":"1","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle and B. Rosenberg, The complexity of computing partial sums off-line,Internat. J. Comput. Geom. Appl. 1 (1991), 33\u201346.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02574385_CR10","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1112\/jlms\/s1-16.4.212","volume":"16","author":"P. Erd\u0151s","year":"1941","unstructured":"P. Erd\u0151s and P. Tur\u00e1n, On a problem of Sidon in additive number theory, and on some related problems,Proc. London Math. Soc. 16 (1941), 212\u2013215.","journal-title":"Proc. London Math. Soc."},{"key":"BF02574385_CR11","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1145\/322276.322281","volume":"28","author":"M. L. Fredman","year":"1981","unstructured":"M. L. Fredman, A lower bound on the complexity of orthogonal range queries,J. Assoc. Comput. Mach. 28 (1981), 696\u2013705.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02574385_CR12","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1137\/0220055","volume":"20","author":"S. Ghosh","year":"1991","unstructured":"S. Ghosh and D. Mount, An output-sensitive algorithm for computing visibility graphs,SIAM J. Comput. 20 (1991), 888\u2013910.","journal-title":"SIAM J. Comput."},{"key":"BF02574385_CR13","volume-title":"An Introduction to the Theory of Numbers","author":"G. Hardy","year":"1959","unstructured":"G. Hardy and E. Wright,An Introduction to the Theory of Numbers, Oxford University Press, London 1959."},{"key":"BF02574385_CR14","first-page":"23","volume":"2","author":"G. Katona","year":"1967","unstructured":"G. Katona and E. Szemer\u00e9di, On a problem in a graph theory,Studia Sci. Math. Hungar. 2 (1967), 23\u201328.","journal-title":"Studia Sci. Math. Hungar."},{"key":"BF02574385_CR15","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1090\/S0002-9947-1938-1501951-4","volume":"43","author":"J. Singer","year":"1938","unstructured":"J. Singer, A theorem in finite projective geometry and some applications to number theory,Trans. Amer. Math. Soc. 43 (1938), 377\u2013385.","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF02574385_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02579163","volume":"4","author":"Z. Tuzua","year":"1984","unstructured":"Z. Tuzua, Covering of graphs by complete bipartite subgraphs: complexity of 0\u20131 matrices,Combinatorica 4 (1984), 111\u2013116.","journal-title":"Combinatorica"},{"key":"BF02574385_CR17","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(85)90044-4","volume":"20","author":"E. Welzl","year":"1985","unstructured":"E. Welzl, Constructing the visibility graph forn line segments inO(n 2) time,Inform. Process. Lett. 20 (1985), 167\u2013171.","journal-title":"Inform. Process. Lett."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574385.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02574385\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574385.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T04:37:07Z","timestamp":1736915827000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02574385"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF02574385"],"URL":"https:\/\/doi.org\/10.1007\/bf02574385","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]},"assertion":[{"value":"16 March 1993","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 1994","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 1994","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}