{"entities":{"Q680154":{"pageid":682003,"ns":120,"title":"Item:Q680154","lastrevid":63540051,"modified":"2026-04-11T13:51:13Z","type":"item","id":"Q680154","labels":{"en":{"language":"en","value":"Flips in edge-labelled pseudo-triangulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6828439"}},"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":"Q680154$2836A701-8E6D-4E93-94BD-8E5D0209EF9C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"59b05adaab562fb5e2527b6c0009b1178b703c4e","datavalue":{"value":{"text":"Flips in edge-labelled pseudo-triangulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q680154$3A076C4C-08D2-4E95-A364-28D17402B7DD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d23570f9b9faef007cf880ebba70140a939aa1b","datavalue":{"value":"1396.65035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680154$DC8740D4-65A8-4CFE-B601-0C03CEDD59DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"22f6b12f56f2aa9fd0d8aea816f351f53d73fd4f","datavalue":{"value":{"entity-type":"item","numeric-id":223040,"id":"Q223040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$70DA6934-06F7-4340-A96B-BA3295D20821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8064abc46f57544018297b9abf19d88992fa3445","datavalue":{"value":{"entity-type":"item","numeric-id":390116,"id":"Q390116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$DBD0EF21-DF2A-4476-BC4F-49E7A688BA91","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":"Q680154$45EA42B1-EDAC-4F96-B23A-CBE5A14744AF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"95b522232ea59b3ec56dcb082cdf4e0641310e1b","datavalue":{"value":{"time":"+2018-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q680154$E40C192B-AB8C-4286-AA11-4E9559FBBC8D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8e946d828761cbe719aaac3de2e09444bf280f26","datavalue":{"value":"https://arxiv.org/abs/1512.01485","type":"string"},"datatype":"url"},"type":"statement","id":"Q680154$EC65159F-9CD3-4642-AC9F-158A560CE819","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2c96e1f5976360f3b64b613cab038c33b567a7ad","datavalue":{"value":"The authors study particular pseudo-triangulations in the plane. A simple polygon with three convex interior angles that are connected by reflex chains is called a pseudo-triangle. Given a set \\(P\\) of \\(n\\) points in the plane, a pseudo-triangulation of \\(P\\) is a subdivision of its convex hull into pseudo-triangles. It is a pointed pseudo-triangulation if all vertices are incident to a reflex angle in some face. Moreover, a triangulation is edge-labelled if each edge has a unique label.  Different kinds of edge flips can be used to transform one pseudo-triangulation into another such triangulation. The authors show that \\(O(n^2)\\) exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. Moreover, using insertion, deletion and exchanging flips, they show that any edge-labelled pseudo-triangulation can be transformed into any other with \\(O(n \\log c + h \\log h)\\) flips, where \\(c\\) is the number of convex layers and \\(h\\) is the number of points on the convex hull.","type":"string"},"datatype":"string"},"type":"statement","id":"Q680154$36C92F33-BCAE-4C88-BF54-879A02D56169","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e4265a5412a56b6039db9291cd3f30418db99670","datavalue":{"value":{"entity-type":"item","numeric-id":247401,"id":"Q247401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$2851371F-B654-4EE3-BF8F-675BFF4E53CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680154$DF24BE93-C613-4613-87C8-9F127A2F7499","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c86301fd5616fa806d6cf0fb5e1268c16253379f","datavalue":{"value":"6828439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680154$4AA4A7D2-594E-4F71-A72B-CFB6899EFB4B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a3a20d0bf8e8de80901988c1c54ad6b0f2eda96","datavalue":{"value":"edge flip","type":"string"},"datatype":"string"},"type":"statement","id":"Q680154$067C433C-162C-4CC5-B43C-1D06AF1A637F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"528ec0417047e65ae33921e0f888a35946d8dcad","datavalue":{"value":"diagonal flip","type":"string"},"datatype":"string"},"type":"statement","id":"Q680154$C4D90C21-89DB-4DF9-ACF2-2D77F803C7DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e00c6bbd9c1c3b619914230f6ec540f943924d4","datavalue":{"value":"pseudo-triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q680154$CE60A113-6A92-4DDF-A16A-15718016C1D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73e9c9bbb86089a840121b486066461ae7c7e2de","datavalue":{"value":"edge-label","type":"string"},"datatype":"string"},"type":"statement","id":"Q680154$AB8AF441-A5CA-48A5-88FD-8AF3F3018AFA","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":"Q680154$CB59A537-9A39-4840-9228-412EF6386040","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac3303da9ca95d93ab8b3460a2fd416ca9466ff8","datavalue":{"value":"W2263302607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680154$1A5DA4A0-92D6-4940-B8A2-34E010437E6C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf91172ac9b2fd6546fd05a4d083e1bdf0d740e","datavalue":{"value":{"entity-type":"item","numeric-id":4818544,"id":"Q4818544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$75616DA8-729B-47E4-8221-EDFAF6495C7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb2dc18a97fe6ed0109111db9361b4609058b3f6","datavalue":{"value":{"entity-type":"item","numeric-id":5896799,"id":"Q5896799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$6C61AC58-AE14-4789-9669-0C722851F24C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85ac0a8041b05737f5b3ae9b71bff7ba85bba507","datavalue":{"value":{"entity-type":"item","numeric-id":3514529,"id":"Q3514529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$A07775F8-FA89-4114-A4B5-8E713991C91C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9618e14b022028b198307029459f867a79cdd5b6","datavalue":{"value":{"entity-type":"item","numeric-id":2557708,"id":"Q2557708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$726D554E-3191-4DC6-A8B4-CF434309C6DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69ec3440191b0e17103361b5c14030c598092c18","datavalue":{"value":{"entity-type":"item","numeric-id":1807608,"id":"Q1807608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$267376EE-4006-4301-8CC7-597272572F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e63d823b34ccf6481c5cea7ac5b798852956de2","datavalue":{"value":{"entity-type":"item","numeric-id":2390240,"id":"Q2390240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$C3D2089F-9A20-4FE5-A6C6-8B9FC889FC17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8a302691e7318b2afab2a1119b67d8426b2e3cf","datavalue":{"value":{"entity-type":"item","numeric-id":4441896,"id":"Q4441896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$1774405C-C9AF-400F-BE6F-80D646489BD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec22232a33befa73f5f254a35056ccc2a1d8530a","datavalue":{"value":{"entity-type":"item","numeric-id":1044747,"id":"Q1044747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$1284BA46-3488-4FD0-B18F-C0B9121A12A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1c1ec2dc6382c156463bd6b00a0654d40ca3f61","datavalue":{"value":{"entity-type":"item","numeric-id":472171,"id":"Q472171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$3310C6D9-987A-4E38-B5E2-DA97058A2E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62fd8e8936ae5e996a9e7264bf82bdfe33fd745c","datavalue":{"value":{"entity-type":"item","numeric-id":1699301,"id":"Q1699301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680154$5C1DE456-EA64-41B5-8B5B-B61DCA923586","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bfcd793474dcc1c9e61f07966850fc80c3d48aed","datavalue":{"value":"10.1016/J.COMGEO.2016.08.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680154$B7130D57-1AF3-4646-BF06-53CB385BD58E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c8d06b82a62546cc909e9a0a2692b15974f71d9","datavalue":{"value":{"entity-type":"item","numeric-id":4434784,"id":"Q4434784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fef941989497b6c8d38e710992d98d7a92986443","datavalue":{"value":{"amount":"+0.8814101219177246","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":"Q680154$6510A184-F5F9-4BCB-807A-1445D238239D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29ab75cce012e71694afb88eaa97d498f1b31396","datavalue":{"value":{"entity-type":"item","numeric-id":2390240,"id":"Q2390240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97e63b09c5154e45aa0e310a9ffcc991f933c849","datavalue":{"value":{"amount":"+0.8800118565559387","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":"Q680154$974CC35F-B0E6-41F4-A59D-1D090D257481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5535d67092821441fc2c631404a35918bc45a35b","datavalue":{"value":{"entity-type":"item","numeric-id":1807608,"id":"Q1807608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1afc36b5143daae7a550a16a81691fe0b329dfaa","datavalue":{"value":{"amount":"+0.8355187773704529","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":"Q680154$3C142138-0785-4A53-839B-BEA13B4ABECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d598ca32ff47b85f84aa390cb98499467af9258e","datavalue":{"value":{"entity-type":"item","numeric-id":1776895,"id":"Q1776895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"379639f0c51979abd4132766a4914f15d1431f66","datavalue":{"value":{"amount":"+0.8340609073638916","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":"Q680154$7725478D-FED0-4296-A97C-FA56430E8656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bc6b41c09048f94ff07857361e44aac611c9d0d","datavalue":{"value":{"entity-type":"item","numeric-id":5460895,"id":"Q5460895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f57d759f7ca1010b39926996a39326b53d51ea3","datavalue":{"value":{"amount":"+0.832015335559845","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":"Q680154$8609C0A6-D43E-4AB0-BA53-9EB3AA21DF84","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Flips in edge-labelled pseudo-triangulations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Flips_in_edge-labelled_pseudo-triangulations"}}}}}