{"entities":{"Q340542":{"pageid":342309,"ns":120,"title":"Item:Q340542","lastrevid":61088925,"modified":"2026-04-10T21:06:29Z","type":"item","id":"Q340542","labels":{"en":{"language":"en","value":"Optimal randomized incremental construction for guaranteed logarithmic planar point location"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6652733"}},"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":"Q340542$37B0AC75-C615-4BBC-8281-2805B33FB49B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c3ffc18f08d4e6ae8878479f47963518383ec977","datavalue":{"value":{"text":"Optimal randomized incremental construction for guaranteed logarithmic planar point location","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q340542$7974721A-93BD-4386-BEE6-FEC1B780EC25","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"16d02e7ad73c27d00bf2e8673aeb727d695688ec","datavalue":{"value":"1357.65023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q340542$1A0A3ED0-9EDA-476D-820B-3BCCEDE7EEDA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"53f803f752cbc83717ed3e7dc1bd7718f771094a","datavalue":{"value":{"entity-type":"item","numeric-id":340540,"id":"Q340540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$5E8E2C3C-B977-4342-B24C-FCAB87CBC1EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4413e07a4bc5255bba695f2ff9fcd71e9e80e21","datavalue":{"value":{"entity-type":"item","numeric-id":340541,"id":"Q340541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$E8508B42-47B3-4AC8-B0AF-BAE94A1930D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"23a41a6deabd7061042ee0e831f408aaabaf33af","datavalue":{"value":{"entity-type":"item","numeric-id":238435,"id":"Q238435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$234436A1-DB7E-41AB-87FA-797869FDF57E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$7C4E6DC1-E7A6-42F8-8949-26EB1E403620","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ca30b16ff66347882421f9615cba4ffa296b704","datavalue":{"value":{"time":"+2016-11-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q340542$0B8736F4-31E4-4B82-8590-03944FF8DE2A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"224d7392ae1b7638769d76b140d7cfe44395255b","datavalue":{"value":"https://arxiv.org/abs/1410.5602","type":"string"},"datatype":"url"},"type":"statement","id":"Q340542$6566DF58-A3A4-4C32-95C1-A872300CB1F0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a1389b63b6e7a815ce4543f6fe3c601a072cc6bb","datavalue":{"value":"The paper deals with one of the fundamental problems in computational geometry, namely with the planar point location. The authors revisit the randomized incremental construction of the trapezoidal map and the related search structures. At the beginning the authors describe the basic random incremental construction in which a trapezoidal map \\(T\\) is constructed and a directed acyclic graph \\(G\\) is maintained during the incremental construction. Moreover, some discussion on guaranteeing the logarithmic query time is made. Next, the authors study the depth \\(D\\) of \\(G\\) and the longest search path \\(L\\) in \\(G\\). They prove that the worst-case ratio between \\(D\\) and \\(L\\) can be \\(\\Theta(n / \\log n)\\), where \\(n\\) is the number of pairwise interior disjoint \\(x\\)-monotone curves inducing the planar subdivision. Later, they prove that there exists a bijection among all search paths in \\(G\\) and those in \\(T\\). Using these results the authors propose an algorithm for the construction of a trapezoidal map that has an expected \\(O(n \\log n)\\) preprocessing time, an expected \\(O(\\log n)\\) query time and requires an expected \\(O(n)\\) space.","type":"string"},"datatype":"string"},"type":"statement","id":"Q340542$2FD3BC18-124E-45D6-83B2-00157F466DEB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q340542$CEB84CF9-174F-4B7B-A268-983C99E32292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q340542$08859564-6D8B-462B-91CF-6B6B768D39F1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6d1f1929da1fa249a020a07ffa647ed69283bd99","datavalue":{"value":"6652733","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q340542$24280E93-5879-47BA-868C-2DC6AF778E02","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e930e55642692c0a336297e3fc16edcba6735e52","datavalue":{"value":"point location","type":"string"},"datatype":"string"},"type":"statement","id":"Q340542$C39D4173-1B13-422F-80EA-94B4B2C0F250","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9e35d6c3318040b64771639cb9cc8dafefc1ca1","datavalue":{"value":"randomized incremental construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q340542$64DDB50C-1C93-4F1B-9AE5-B5C9399760A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac3685cb1fd95e88c1ebdfeb0f7b67d4fa077f52","datavalue":{"value":"trapezoidal map","type":"string"},"datatype":"string"},"type":"statement","id":"Q340542$6410C628-6415-4F19-A92C-76BCEB30D904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q340542$5CB5691B-161A-4C36-B2F8-07DAD3210DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b30413bdc80736aeecdc7f80229ac89c0446304","datavalue":{"value":"directed acyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q340542$B87D5B7C-ABFD-45E6-A3BF-54B780B6357F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e8aff2b8e51ed9533d593cc755cbfae6f7c82e5","datavalue":{"value":{"entity-type":"item","numeric-id":305012,"id":"Q305012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$FF6E217F-77F8-4981-914C-B47282E1A3F3","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"be8017d9dbdcd2a09b059a0646cab651cb922afd","datavalue":{"value":{"entity-type":"item","numeric-id":12888,"id":"Q12888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$8192B746-50D6-4F52-A957-764FD6E56E75","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":"Q340542$BAD56E42-5CE7-41F2-B02C-5F63E9DEAFC7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"672adf9a45f11825d22cfbde80387919b6f2ddd2","datavalue":{"value":"W1836974482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q340542$D36755C4-3D6F-4DB9-9EF0-E776FA44CFBD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7c73bf67fd833bb5bb4fe98c57aa453c64b7ab6","datavalue":{"value":{"entity-type":"item","numeric-id":2768303,"id":"Q2768303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$C1BB3B46-BDEA-4953-AA58-9989235DEFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33de0de0cb9f5e9b448131322f026f18fa537173","datavalue":{"value":{"entity-type":"item","numeric-id":2768304,"id":"Q2768304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$6A08F20A-3C9B-4C56-9B8D-1765F8DE66BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4241f8308d167565bbead4d0eec3525ac106e02b","datavalue":{"value":{"entity-type":"item","numeric-id":5452284,"id":"Q5452284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$CFD1C11B-D308-4C0F-8A2F-6C6A7D6B50F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a317bc1c9722164c0184ade33e7888197abc4ef","datavalue":{"value":{"entity-type":"item","numeric-id":3021945,"id":"Q3021945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$FF1F215C-AC5A-4901-A1CC-E9D1545B66EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2498a66f91f7d57dee09c9b48765ac68ca4fb4dc","datavalue":{"value":{"entity-type":"item","numeric-id":4099207,"id":"Q4099207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$991E7196-31E7-4F99-A912-0DA996B5FCBF","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":"Q340542$3B5CDD8B-77B8-4AE8-B94F-33AE04E397BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23e167117738e3d87e173766957800ef9ca8426a","datavalue":{"value":{"entity-type":"item","numeric-id":5463410,"id":"Q5463410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$FA0CD6D8-3CC3-4F5B-AC60-555545A99FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d38e6dcd68e0f7af0e2ea641bd29c7a3739a44ea","datavalue":{"value":{"entity-type":"item","numeric-id":625322,"id":"Q625322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$A6890216-DC65-4570-8335-645E23CCB966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed2ed55faf3c9ec0b519578931b1bd560412d698","datavalue":{"value":{"entity-type":"item","numeric-id":4507335,"id":"Q4507335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$20927E6B-1CA0-42A5-8AF9-39A36FDF4E9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"885450f84f476fc50e5421777f794aba1332848d","datavalue":{"value":{"entity-type":"item","numeric-id":2912879,"id":"Q2912879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$C116027A-51A9-4BEA-AFF2-01B8BBAB75CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d030a662d19196eb5bfed5d3c606d0de377f779c","datavalue":{"value":{"entity-type":"item","numeric-id":340542,"id":"Q340542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$2117EBC7-FFBF-44EE-ADDF-0D3D6EFC41FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"813773fa16a57d5ba1f1f634d7f3bafad0c0476d","datavalue":{"value":{"entity-type":"item","numeric-id":3967063,"id":"Q3967063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$75FD36F1-3FB2-4CB3-9773-7B1B39F39C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1be902ee3eb6f7115793fc4afe9bd6110bd412c","datavalue":{"value":{"entity-type":"item","numeric-id":4133115,"id":"Q4133115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$A340A692-CE7B-4D26-B3E2-26555B0E0BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70319c6dae513609b751e1310ee2ca78c3ba8d69","datavalue":{"value":{"entity-type":"item","numeric-id":2638830,"id":"Q2638830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$B099D884-8043-489B-A4C6-56C86F5A31BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1e47db404a66af96a3730bbe2dc8a0b28aa48b","datavalue":{"value":{"entity-type":"item","numeric-id":3912042,"id":"Q3912042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$1F5FED17-A640-467E-BCA9-6349F895BDF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a39eec153bd718a2c45744698baf06a8502d8bf9","datavalue":{"value":{"entity-type":"item","numeric-id":809630,"id":"Q809630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$C6C6B639-31E3-4AC6-B343-134BA4363531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"446454aad6e7b10e76ccc3470da7b873ca5981f4","datavalue":{"value":{"entity-type":"item","numeric-id":4512577,"id":"Q4512577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q340542$49E9ED79-BA4B-4EBB-856B-F4FEF9B1C84A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4971f52177334a4ac09d85ec4f962acbf4da4db7","datavalue":{"value":"10.1016/J.COMGEO.2016.07.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q340542$47BA5425-C697-4F37-94B1-CCC8A73A084A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ea1d72cfdeae09d2c43347d9df32d04ba8bc571","datavalue":{"value":{"entity-type":"item","numeric-id":2721994,"id":"Q2721994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f812dd2dca14a8161b8d30631c4ea223aa484b29","datavalue":{"value":{"amount":"+0.8059441447257996","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":"Q340542$A76C4B1F-E84E-4C82-A3CF-59DA8A391ED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f33ea979f7c153159cac702e3ac6f6d78647b1c","datavalue":{"value":{"entity-type":"item","numeric-id":3558019,"id":"Q3558019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f812dd2dca14a8161b8d30631c4ea223aa484b29","datavalue":{"value":{"amount":"+0.8059441447257996","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":"Q340542$A7D49C85-1373-48F0-95C4-4989DCDDD5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48e8a050aa145b2ab064e83fa229b57484f4c5e2","datavalue":{"value":{"entity-type":"item","numeric-id":4562277,"id":"Q4562277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c029a16e70303bdd5e9180c603ee231896dc2a5","datavalue":{"value":{"amount":"+0.7953428030014038","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":"Q340542$8286A608-29FF-4A34-ADBE-49FD14541B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2af0aa7f0ac63a5402f0e6f82df56c79ae9a0438","datavalue":{"value":{"entity-type":"item","numeric-id":5370568,"id":"Q5370568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e431807aafb0cd6016492f765afd6271fd49e5d","datavalue":{"value":{"amount":"+0.7855966091156006","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":"Q340542$3E67AD1E-6C77-411A-A16F-D91DFF042420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4fca312d0504dac575efe37d17bd277dc75b255","datavalue":{"value":{"entity-type":"item","numeric-id":2768304,"id":"Q2768304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db3efe27bb6e855f6d3351c31d6757191b2eb0f3","datavalue":{"value":{"amount":"+0.782232403755188","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":"Q340542$2D6A3E92-BA9D-482C-9660-7712854EF40D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal randomized incremental construction for guaranteed logarithmic planar point location","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_randomized_incremental_construction_for_guaranteed_logarithmic_planar_point_location"}}}}}