{"entities":{"Q1122981":{"pageid":1133730,"ns":120,"title":"Item:Q1122981","lastrevid":49292986,"modified":"2026-01-06T22:16:06Z","type":"item","id":"Q1122981","labels":{"en":{"language":"en","value":"Topologically sweeping an arrangement"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4108149"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$C03D17DE-12B2-4431-BD76-127F4DC9CD89","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6fa0037cb0212f52b56dd67f404ff2404b482853","datavalue":{"value":{"text":"Topologically sweeping an arrangement","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122981$9D637178-DB93-435A-9B56-909F7E6F0021","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"909c24f2efa50d019cbc9dcbd980b75f2e78c9d5","datavalue":{"value":"0676.68013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122981$965A6876-0115-4FFA-9753-06B1FD1555A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df647c488fa13004e76b622a5c622ab733ee9a6a","datavalue":{"value":"10.1016/0022-0000(89)90038-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122981$C10022A6-18DF-4957-BD82-567B10246CA6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a06f7d76e1dbfa89a80e5d40561052d9e137ca58","datavalue":{"value":{"entity-type":"item","numeric-id":242843,"id":"Q242843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$3D5E0796-42C7-42B6-A3E3-211CA57D4FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27055c7a0af767b1f36b14e7674bc0aa2224fdc0","datavalue":{"value":{"entity-type":"item","numeric-id":534491,"id":"Q534491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$11EA6F53-AB9B-4B1B-9691-A291E21C0DD9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$4631A2C3-DBFF-41BC-87C3-1932E6EFCFD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1122981$F2EFCFC0-181E-4ED1-8FED-5D8B779FE73E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9f4a497c2178d42d5d2ec77510f64c2d9d953165","datavalue":{"value":"Many computation geometric problems in the plane may be solved by constructing and searching planar line arrangements, see e.g. papers by \\textit{B. Chazelle}, \\textit{L. Guibas}, \\textit{D. T. Lee} [BIT 25, 76-90 (1985; Zbl 0603.68072)] and \\textit{H. Edelsbrunner}, \\textit{J. O'Rourke}, \\textit{R. Seidel} [SIAM J. Comput. 15, 341-363 (1986; Zbl 0603.68104)] where optimal \\(0(n^ 2)\\) time and space algorithms are given for constructing planar line arrangements. In many cases, however, it turns out that one actually needs not to construct the whole arrangement explicitly but rather enumerate its elements in some (partial) order.    The present paper gives an algorithm to accomplish this using only 0(n) space. The method used is the generalization of the well-known sweepline paradigm called topological line sweep where the topological line may be viewed as a y-monotone curve moving from left to right not as a whole but ``stretching out'' in amoeba-like way. This leads to space or/and time improvements for a number of problems discussed in the paper. See also the paper of \\textit{L. Guibas}, \\textit{R. Seidel} [Discrete Comput. Geom. 2, 175-193 (1987; Zbl 0623.68043)] for another implementation of the topological sweep for overlaying planar convex maps in time linear in the \\(input+output\\) size.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122981$659543A3-10CC-44AD-B0CE-D408ADBF43C5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122981$10E86EA2-05CF-47E1-92C3-AC5E24694268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122981$E6C530E1-EE83-42BB-A98C-E9D8482965F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee1b08e7ce1ed2e3448188011bd4b1917cf7f174","datavalue":{"value":"4108149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122981$DC684B68-267E-4D81-A42B-66CB3918B073","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122981$018BB6C1-9C22-4AD5-B97D-B8A33D87A0AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d4a1607cb89ff4af124295f6c6ee11406f86f6f","datavalue":{"value":"topological sweep","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122981$F8EB5F0D-6E02-4E54-B402-274C80AAD068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8ba660c67564903836219759b7d1493891e1973","datavalue":{"value":"duality transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122981$961E76BB-AC35-4783-8C45-2D24B788DAE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57c13caa9d3cb41a8450228aa4d17e8f45c29e7b","datavalue":{"value":"amortized complexity analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122981$946A5620-75E5-4B90-BB02-CBED68133C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c1707b7c039a5fd0c982b1aac0cc40d782f6b67","datavalue":{"value":"line arrangements","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122981$D62BC254-7998-44A8-9994-5821B0DE0E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e16149051ab90648e4bbbf397c04fb68358880f","datavalue":{"value":"sweepline paradigm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122981$5548846D-D546-460B-BE1A-2E47ADAEF58D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1465d96732bfc372bdbe9372614e9f71fed0e389","datavalue":{"value":"Q56442903","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122981$F41DE38C-B127-4D9B-BBD8-CAFEEB7B5EE9","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$6F5AD301-F53C-42D7-B512-21410474B185","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$69A35911-16FF-4B61-9D80-6542ECBEF6AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ce89c39eded45d5a7a9d9cb06ace1eda77c8a8","datavalue":{"value":{"entity-type":"item","numeric-id":3911409,"id":"Q3911409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$3E56EE77-DF73-4248-9AFC-CCF47E9DC5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb71e38ab0216024ec0690b1685e409899a3aead","datavalue":{"value":{"entity-type":"item","numeric-id":1082821,"id":"Q1082821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$05D45D4A-697B-403B-B816-61B0EBBBA4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5abe187468fda1ca85bd2c0f54c1e2fcfb11f0d","datavalue":{"value":{"entity-type":"item","numeric-id":3928584,"id":"Q3928584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$CA595BC3-4740-4210-A2AF-0FA942667EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$CE9C438E-DD62-48D3-90DC-18087C77660B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29b8e47936578f5cad24b50941e85f6a32ad9da","datavalue":{"value":{"entity-type":"item","numeric-id":3738618,"id":"Q3738618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$1AC02270-2E4C-404A-9B04-FA5FE9FB95E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0bb2a78ba34e8728e91d77da2bf6df4e36bb56c","datavalue":{"value":{"entity-type":"item","numeric-id":3740283,"id":"Q3740283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$8C90A65D-E7A2-4DBA-845E-C177D617F3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e8a40e3dbf619b683566bb917169675f46246dd","datavalue":{"value":{"entity-type":"item","numeric-id":3286826,"id":"Q3286826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$B7CD5D02-F698-451E-86F4-F6E3B5902221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da92b4d12846aa1606fa89a7ac5ca00163d7fc64","datavalue":{"value":{"entity-type":"item","numeric-id":4720805,"id":"Q4720805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$536BB187-0853-4A74-810A-36AC5DF7ED2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46217ac19b442b8eee6f5dd5a82ca9d2be06b1a2","datavalue":{"value":{"entity-type":"item","numeric-id":1226391,"id":"Q1226391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$DCE4FCF9-97C6-477F-9A0B-5523411375A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"204b880daa551e1a1bce9c11a1a3d898d8fae13a","datavalue":{"value":{"entity-type":"item","numeric-id":5663020,"id":"Q5663020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$7F07266D-290F-4EA6-9EE0-095F847D2B22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff4e812fbcc008a1d5259e712cd9203d973f596","datavalue":{"value":{"entity-type":"item","numeric-id":3711764,"id":"Q3711764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$85DE6490-C927-48D3-BB4F-0F1FAAFE1768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9ef1ddad18a2d517ded8d358f3690d57f482b45","datavalue":{"value":{"entity-type":"item","numeric-id":1253812,"id":"Q1253812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$E89C1821-3C5D-4B63-9117-90AEA97C0607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a6175dab652551b56ea1ab3e59569e9c643ea56","datavalue":{"value":{"entity-type":"item","numeric-id":3670079,"id":"Q3670079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$7928B058-F7BD-4D47-95F2-A304F7A29871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"085e1218a66243e307498d7e8b0c1d323937d638","datavalue":{"value":{"entity-type":"item","numeric-id":3337244,"id":"Q3337244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$05159AA3-8669-4282-9E66-787B3237C07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a424f44a8dbc665539390a6f9c8785edbdbed5f3","datavalue":{"value":{"entity-type":"item","numeric-id":3953198,"id":"Q3953198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$147AC812-9081-4DCC-86DD-AF99602DA9A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08bbfa2750c080ec67d6b7bc35b58e0a9bc36c96","datavalue":{"value":{"entity-type":"item","numeric-id":3694703,"id":"Q3694703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$44C00AB9-72BC-4094-9A71-B12BD3B082E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00910816ba034b6655b7a47d13d1206cc1d40ae2","datavalue":{"value":{"entity-type":"item","numeric-id":3735083,"id":"Q3735083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$F09567F4-DAF4-442E-92EA-EB86C301121C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ffec4d94b7b012095f39126ed96f3bf822347da","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122981$F8FC6878-2B20-486B-9AA3-3E1C3D9880B4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ef9b0b97a3da182fd77b886f9a51884a077fe597","datavalue":{"value":"https://doi.org/10.1016/0022-0000(89)90038-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1122981$78FEF4FD-A4A4-4006-A147-671E22FAC6DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"979719609b850bb0a6bfbc7ae55deba56ad89045","datavalue":{"value":"W4213074663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122981$DCA6C3AB-4598-40B5-A97A-35D6F3BEBAF5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48342537a955ab5d15038ce9aafd07d79151d553","datavalue":{"value":{"entity-type":"item","numeric-id":1107313,"id":"Q1107313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ecbc62cba7580c66ca41533e3fcdf81899626ac","datavalue":{"value":{"amount":"+0.8284322023391724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122981$C292D47D-9E4C-4EEC-AB62-990ECA2CD71B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a462ba34a76cc52593f5c8b0ba8ec4ea43d06b01","datavalue":{"value":{"entity-type":"item","numeric-id":4312275,"id":"Q4312275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ff02d7dfb94acab506497af0f6ac338ec0477ef","datavalue":{"value":{"amount":"+0.8119803071022034","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122981$FEB2A8BA-FD01-4F2D-B334-9B35F7467CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d915d9be578818d8278510ff69431586b1269b4","datavalue":{"value":{"entity-type":"item","numeric-id":4636513,"id":"Q4636513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"358b715b471ae9def60da1be5006f387afae2ea8","datavalue":{"value":{"amount":"+0.8118590712547302","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122981$F5C92814-A717-41F5-AE74-E52AC2A50447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c494ec22bcc0e24d2ce94525544ae33aa552c59","datavalue":{"value":{"entity-type":"item","numeric-id":3795219,"id":"Q3795219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4f160166a3b4efaf3f01e8e4532c953ad762b59","datavalue":{"value":{"amount":"+0.8111546039581299","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122981$BDE7D70F-2F7B-4ACB-814F-F112B9DFE797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9dd19ab63085f70ba56187a69a50135ad08554e3","datavalue":{"value":{"entity-type":"item","numeric-id":3997899,"id":"Q3997899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"314f50850f8b3624e74dbf08dd0a5f0cabcbd02d","datavalue":{"value":{"amount":"+0.8102198243141174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122981$1A547EB6-8C7E-4659-B663-32988D718A3A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1122981","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1122981"}}}}}