{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,28]],"date-time":"2024-07-28T19:50:58Z","timestamp":1722196258493},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1990,6,1]],"date-time":"1990-06-01T00:00:00Z","timestamp":644198400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1990,6]]},"DOI":"10.1007\/bf02123007","type":"journal-article","created":{"date-parts":[[2005,9,14]],"date-time":"2005-09-14T11:22:12Z","timestamp":1126696932000},"page":"137-173","source":"Crossref","is-referenced-by-count":37,"title":["Triangles in space or building (and analyzing) castles in the air"],"prefix":"10.1007","volume":"10","author":[{"given":"B.","family":"Aronov","sequence":"first","affiliation":[]},{"given":"M.","family":"Sharir","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02123007_CR1","doi-asserted-by":"crossref","unstructured":"B.Aronov, H.Edelsbrunner, L. J.Guibas, and M.Sharir:Improved bounds on the number of edges of many faces in arrangements of line segments. Manuscript, 1989.","DOI":"10.1145\/73393.73399"},{"key":"BF02123007_CR2","unstructured":"B.Aronov, and M.Sharir:The union of convex polyhedra and translational motion planning, in preparation."},{"key":"BF02123007_CR3","doi-asserted-by":"crossref","unstructured":"B.Chazelle, and J.Friedman: A deterministic view of random sampling and its use in geometry, InProc. 29th IEEE Symp. on Foundations of Computer Science, 1988, 539\u2013549.","DOI":"10.1109\/SFCS.1988.21970"},{"key":"BF02123007_CR4","doi-asserted-by":"crossref","unstructured":"B.Chazelle, and L.Palios:Triangulating a non-convex polytope, Proc. 5th Symp. on Computational Geometry,1989, 393\u2013400.","DOI":"10.1145\/73833.73876"},{"key":"BF02123007_CR5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. Clarkson","year":"1987","unstructured":"K. Clarkson: New applications of random sampling in computational geometry,Discrete Comput. Geom.,2 (1987) 195\u2013222.","journal-title":"Discrete Comput. Geom."},{"key":"BF02123007_CR6","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. Clarkson","year":"1990","unstructured":"K. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, andE. Welzl: Combinatorial complexity bounds for arrangements of curves and surfaces,Discrete Comput. Geom.,5(1990) 99\u2013160.","journal-title":"Discrete Comput. Geom."},{"key":"BF02123007_CR7","doi-asserted-by":"crossref","unstructured":"G. E.Collins: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, In2nd GI Conference on Automata Theory and Formal Languages, Springer,1975, 134\u2013183.","DOI":"10.1007\/3-540-07407-4_17"},{"key":"BF02123007_CR8","doi-asserted-by":"crossref","unstructured":"D. P.Dobkin, and M. J.Laszlo: Primitives for the manipulation of three-dimensional subdivisions, InProc. 3rd ACM Symp. on Computatioal Geometry,1987, 86\u201399.","DOI":"10.1145\/41958.41967"},{"key":"BF02123007_CR9","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF02187742","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner, L. J. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, andE. Welzl: Implicity representing arrangements of lines or of segments,Discrete Comput. Geom.,4(1989) 433\u2013466.","journal-title":"Discrete Comput. Geom."},{"key":"BF02123007_CR10","doi-asserted-by":"crossref","unstructured":"H.Edelsbrunner, L. J.Guibas, J.Pach, R.Pollack, M.Sharir, and R.Seidel: Arrangements of curves in the plane: Topology, combinatorics and algorithms, InProc. 15th Int. Colloq. on Automata, Languages and Programming,1988, 214\u2013229.","DOI":"10.1007\/3-540-19488-6_118"},{"key":"BF02123007_CR11","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF02187785","volume":"5","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner, L. J. Guibas, andM. Sharir: The complexity of many cells in arrangements of planes and related problems,Discrete Comput. Geom.,5(1990) 197\u2013216.","journal-title":"Discrete Comput. Geom."},{"key":"BF02123007_CR12","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02187784","volume":"5","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner, L. J. Guibas, andM. Sharir: The complexity and construction of many faces in arrangements of lines and of segments,Discrete Comput. Geom.,5(1990) 161\u2013196.","journal-title":"Discrete Comput. Geom."},{"key":"BF02123007_CR13","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner, L. J. Guibas, andM. Sharir: The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications, Tech. Report 333, Comp. Sci, Dept., Courant Institute, November1987.Discrete Comput. Geom. 4(1989) 311\u2013336.","journal-title":"Discrete Comput. Geom."},{"key":"BF02123007_CR14","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, andR. Seidel: Construsting arrangements of lines and hyperplanes with applications,SIAM J. Computing,15 (1986) 341\u2013363.","journal-title":"SIAM J. Computing"},{"key":"BF02123007_CR15","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0097-3165(86)90078-6","volume":"41","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, andE. Welzl: On the maximal number of edges of many faces in an arrangement,J. Comb. Theory, Ser. A.41 (1986) 159\u2013166.","journal-title":"J. Comb. Theory, Ser. A."},{"key":"BF02123007_CR16","first-page":"459","volume":"7","author":"P. Erd\u0151s","year":"1962","unstructured":"P. Erd\u0151s: On the number of complete subgraphs contained in certain graphs,Publ. Math. Inst. Hungar. Acad. Sci.,7 (1962) 459\u2013464.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"BF02123007_CR17","unstructured":"V.Guillemin, and A.Pollack:Differential Topology, Prentice-Hall,1974."},{"key":"BF02123007_CR18","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"S. Hart, andM. Sharir: Nonlinearity of Davenport-Schinzel sequences and of generalized path-compression schemes,Combinatorica,6 (1986) 151\u2013177.","journal-title":"Combinatorica"},{"key":"BF02123007_CR19","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler, andE. Welzl: Epsilon-nets and simplex range queries,Discrete Comput Geom.,2 (1987) 127\u2013151.","journal-title":"Discrete Comput Geom."},{"key":"BF02123007_CR20","doi-asserted-by":"crossref","unstructured":"J.Matou\u0161ek: Construction of\u03b5-nets, InProc 5th Symp. on Computational Geometry,1989, 1\u201310.","DOI":"10.1145\/73833.73834"},{"key":"BF02123007_CR21","doi-asserted-by":"crossref","unstructured":"E. E.Moise:Geometric Topology in Dimensions 2 and 3, Springer,1977.","DOI":"10.1007\/978-1-4612-9906-6"},{"key":"BF02123007_CR22","unstructured":"J.O'Rourke:Art Gallery Theorems and Algorithms, Oxford University Press,1987."},{"key":"BF02123007_CR23","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF02187732","volume":"4","author":"J. Pach","year":"1989","unstructured":"J. Pach, andM. Sharir: The Upper Envelope of Piecewise Linear Functions and the Boundary of a Region Enclosed by Convex Plates: Combinatorial Analysis,Discrete Comput. Geom. 4(1989) 291\u2013310.","journal-title":"Discrete Comput. Geom."},{"key":"BF02123007_CR24","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF02187902","volume":"3","author":"R. Pollack","year":"1988","unstructured":"R. Pollack, M. Sharir, andS. Sifrony: Separating two simple polygons by a sequence of translations,Discrete Comput. Geom.,3 (1988) 123\u2013136.","journal-title":"Discrete Comput. Geom."},{"issue":"7","key":"BF02123007_CR25","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak, andR. E. Tarjan: Planar point location using persistent search trees,CACM,29 (7) (1986) 669\u2013679.","journal-title":"CACM"},{"key":"BF02123007_CR26","doi-asserted-by":"crossref","unstructured":"M.Sharir, and S.Sifrony: Coordinated motion planning for two independent robots, InProc. 4th ACM Symp. on Computational Geometry,1988, 319\u2013328.","DOI":"10.1145\/73393.73426"},{"key":"BF02123007_CR27","unstructured":"C. D.Thomborson, L. L.Deneen, and G. M.Shute:A uniform representation for partially embedded graphs, Manuscript."},{"key":"BF02123007_CR28","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF02187894","volume":"3","author":"A. Wiernik","year":"1988","unstructured":"A. Wiernik andM. Sharir: Planar realization of non-linear Davenport-Schinzel sequences by segments,Discrete Comput. Geom.,3 (1988) 15\u201347.","journal-title":"Discrete Comput. Geom."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02123007.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02123007\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02123007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T12:39:55Z","timestamp":1626525595000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02123007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["BF02123007"],"URL":"https:\/\/doi.org\/10.1007\/bf02123007","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}