{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:40:12Z","timestamp":1778294412516,"version":"3.51.4"},"reference-count":26,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7868,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1992,1]]},"DOI":"10.1016\/0304-3975(92)90319-b","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:47:37Z","timestamp":1027640857000},"page":"319-336","source":"Crossref","is-referenced-by-count":61,"title":["Arrangements of curves in the plane\u2014topology, combinatorics, and algorithms"],"prefix":"10.1016","volume":"92","author":[{"given":"Herbert","family":"Edelsbrunner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Pollack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raimund","family":"Seidel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(92)90319-B_BIB1","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0097-3165(89)90032-0","article-title":"Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences","volume":"52","author":"Agarwal","year":"1989","journal-title":"J. Combin. Theory, Ser. A"},{"key":"10.1016\/0304-3975(92)90319-B_BIB2","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/BF01840405","article-title":"An optimal algorithm for the boundary of a cell in a union of rays","volume":"5","author":"Alevizos","year":"1990","journal-title":"Algorithmica"},{"key":"10.1016\/0304-3975(92)90319-B_BIB3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02123007","article-title":"Triangles in space or building (and analyzing) castles in the air","volume":"10","author":"Aronov","year":"1990","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(92)90319-B_BIB4","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1109\/SFCS.1988.21975","article-title":"An optimal algorithm for intersecting line segments in the plane","author":"Chazelle","year":"1988","journal-title":"Proc. 29th Ann. IEEE Sympos. Found. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90319-B_BIB5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02238188","article-title":"On a circle placement problem","volume":"36","author":"Chazelle","year":"1986","journal-title":"Computing"},{"key":"10.1016\/0304-3975(92)90319-B_BIB6","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01934990","article-title":"The power of geometric duality","volume":"25","author":"Chazelle","year":"1985","journal-title":"BIT"},{"key":"10.1016\/0304-3975(92)90319-B_BIB7","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02187783","article-title":"Combinatorial complexity bounds for arrangements of curves and spheres","volume":"5","author":"Clarkson","year":"1990","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0304-3975(92)90319-B_BIB8","series-title":"Algorithms in Combinatorial Geometry","author":"Edelbrunner","year":"1987"},{"key":"10.1016\/0304-3975(92)90319-B_BIB9","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02187784","article-title":"The complexity of many faces in arrangements of lines and of segments","volume":"5","author":"Edelsbrunner","year":"1990","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0304-3975(92)90319-B_BIB10_1","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","article-title":"Constructing arrangements of lines and hyperplanes with applications","volume":"15","author":"Edelsbrunner","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90319-B_BIB10_2","first-page":"83","article-title":"Constructing arrangements of lines and hyperplanes with applications","volume":"12","author":"Edelsbrunner","year":"1983","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90319-B_BIB11","first-page":"491","article-title":"On the general motion planning problem with two degrees of freedom","volume":"5","author":"Guibas","year":"1990","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0304-3975(92)90319-B_BIB12","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","article-title":"Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes","volume":"6","author":"Hart","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(92)90319-B_BIB13","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","article-title":"Sorting Jordan sequences in linear time, using level-linked search trees","volume":"68","author":"Hoffman","year":"1986","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(92)90319-B_BIB14","first-page":"136","article-title":"Moving a ladder in three dimensions: Upper and lower bounds","author":"Ke","year":"1987","journal-title":"Proc. 3rd Ann. ACM Symp. on Computational Geometry"},{"key":"10.1016\/0304-3975(92)90319-B_BIB15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02187683","article-title":"On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles","volume":"1","author":"Kedem","year":"1986","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0304-3975(92)90319-B_BIB16","first-page":"371","article-title":"Arrangements of lines in 3-space: A data structure with applications","author":"McKenna","year":"1988","journal-title":"Proc. Ann. 4th ACM Symp. on Computational Geometry"},{"key":"10.1016\/0304-3975(92)90319-B_BIB17","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1109\/SFCS.1988.21974","article-title":"A fast planar partition algorithm I","author":"Mulmuley","year":"1988","journal-title":"Proc. 29th Ann. IEEE Sympos. Found. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90319-B_BIB18","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF02187902","article-title":"Separating two simple polygons by a sequence of translations","volume":"3","author":"Pollack","year":"1988","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0304-3975(92)90319-B_BIB19","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1002\/cpa.3160360305","article-title":"On the piano movers' problem: I. The case of a rigid polygonal body moving amidst polygonal barriers","volume":"36","author":"Schwartz","year":"1983","journal-title":"Comm. Pure Appl. Math."},{"key":"10.1016\/0304-3975(92)90319-B_BIB20","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0747-7171(08)80070-3","article-title":"On the two-dimensional Davenport-Schinzel problem","volume":"10","author":"Schwartz","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/0304-3975(92)90319-B_BIB21","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02579209","article-title":"Almost linear upper bounds on the length of general Davenport-Schinzel sequences","volume":"7","author":"Sharir","year":"1987","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(92)90319-B_BIB22","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02122559","article-title":"Improved lower bounds on the length of Davenport-Schinzel sequences","volume":"8","author":"Sharir","year":"1988","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(92)90319-B_BIB23","unstructured":"P. Shor, Geometric realizations of superlinear Davenport\u2013Schinzel sequences, in preparation."},{"key":"10.1016\/0304-3975(92)90319-B_BIB24","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF02187894","article-title":"Planar realization of nonlinear Davenport-Schinzel sequences by segments","volume":"3","author":"Wiernik","year":"1988","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0304-3975(92)90319-B_BIB25","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","article-title":"Topologically sweeping an arrangement","volume":"38","author":"Edelsbrunner","year":"1989","journal-title":"J. Comput. System. Sci."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290319B?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290319B?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T06:23:55Z","timestamp":1580883835000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759290319B"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["030439759290319B"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(92)90319-b","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1992,1]]}}}