{"entities":{"Q540059":{"pageid":541826,"ns":120,"title":"Item:Q540059","lastrevid":62605164,"modified":"2026-04-11T07:13:27Z","type":"item","id":"Q540059","labels":{"en":{"language":"en","value":"Counting triangulations of planar point sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5903000"}},"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":"Q540059$CDFFBF97-0C32-455E-9B5C-BEBDF5FEA985","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fc933a2d12d275398a82d371c82a963559b18614","datavalue":{"value":{"text":"Counting triangulations of planar point sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q540059$E2543933-22E3-4985-A979-D2659A70E561","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab2fefcf2026d4a26f2a5a15f7d668d21c2ce6d8","datavalue":{"value":"1218.05072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540059$10DEDE55-1C15-4DD1-A2BC-6F0CC2A25384","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05973d4747711a904c4eb354f325fda834906623","datavalue":{"value":{"entity-type":"item","numeric-id":396765,"id":"Q396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540059$897185EC-D076-4220-8EFA-A1B59C519EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c355b865dde6108063edf9eb0320be44dcee3e6","datavalue":{"value":{"entity-type":"item","numeric-id":312144,"id":"Q312144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540059$6C982838-A8DC-4211-A5AC-CB992D63646D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540059$E1F412BA-1214-4D11-BA18-067C6B3A9F50","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca412915d48bc02df19cbc26b81271d64e23ee32","datavalue":{"value":{"time":"+2011-06-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q540059$4E96A0CB-047C-44F5-9DAF-9F8543D25C98","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9ecf199b2cfadcf3d218c6355c107cdb46b7e04b","datavalue":{"value":"https://eudml.org/doc/223107","type":"string"},"datatype":"url"},"type":"statement","id":"Q540059$B62AA85F-2AF7-4872-975B-7EB400A7815D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"31190e295cb7db93418dbd9260cf00cc9fa8dad1","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p70.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q540059$32CC0DDE-6D16-4664-A4E1-BF6100E46DC2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f382d769dfaf97ca90ac792907d8cb2a1e96113","datavalue":{"value":"Summary: We study the maximal number of triangulations that a planar set of \\(n\\) points can have, and show that it is at most \\(30n\\). This new bound is achieved by a careful optimization of the charging scheme of Sharir and Welzl, which has led to the previous best upper bound of \\(43n\\) for the problem.   Moreover, this new bound is useful for bounding the number of other types of planar (i.e., crossing-free) straight-line graphs on a given point set. Specifically, it can be used to derive new upper bounds for the number of planar graphs \\((207.84n)\\), spanning cycles \\((O(68.67n))\\), spanning trees \\((O(146.69n))\\), and cycle-free graphs \\((O(164.17n))\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q540059$EEA5BD9F-1B45-4F28-964A-3CC092CC77F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540059$476A2A8E-01CA-4470-AFCA-C57C007214A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540059$29268FFF-918D-459E-ACBF-16041DEB5BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540059$E67846E9-1E04-4EBB-80DD-58FE5EA5B82E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aa4b9369491fcbe94e44b6d0d64770aa72c87894","datavalue":{"value":"5903000","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540059$0E6C4B17-1028-47D5-B0A1-00FA377D0268","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88244eaf771352cc184de31279f1fe59185b88de","datavalue":{"value":"triangulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q540059$2FBFC923-B818-4C35-B2D1-C16C36F86EE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa64eae916ac50f9d0bdde79696d641a11ea4cba","datavalue":{"value":"counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q540059$2AE5167D-04D2-49F2-96EB-24D3F3AFF445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48d03aa7a27439d9e12d7f27fb2956a119d57567","datavalue":{"value":"charging schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q540059$D75731E4-0EA1-4523-8644-9059C8E087F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0cf49d358ac6b88932ce00a4c338c505680ae80","datavalue":{"value":"crossing-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q540059$66393017-A79E-4CEC-9527-FDFFE474AC71","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":"Q540059$E5E1C244-F4BF-48F7-85CE-E16846EBA6FE","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a2bc53b9fde225c83feb29e5e033e838874cdd97","datavalue":{"value":"bafybeibtbp3vcawefakjkr3goemfszkvblycl545f3qxvfgzkyr67hwc7q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540059$0FCD604B-BC09-4C32-9601-657ADD6281AB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f61eadfa9d2a1a15f1aa9dfad24ed36df37efbb","datavalue":{"value":{"entity-type":"item","numeric-id":1873821,"id":"Q1873821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"512849ab44f56928afb9ca07a5ecd2f04389a3f1","datavalue":{"value":{"amount":"+0.8781031966209412","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":"Q540059$202E9C21-648C-41B0-A42C-1AE3E8B7E665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0614e5948acdd3bd210aba5e016805dcf76cbcb","datavalue":{"value":{"entity-type":"item","numeric-id":5174454,"id":"Q5174454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53fa36ad87df99619d205a564a17b83d54c92895","datavalue":{"value":{"amount":"+0.8753966093063354","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":"Q540059$8F5CB1B3-69B7-492E-8E86-EB289E8C28CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a87007b0030571329e81503383fa6bb85460f86c","datavalue":{"value":{"entity-type":"item","numeric-id":1288910,"id":"Q1288910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09b4572c882de81aeb2d14e2648947e7ac857966","datavalue":{"value":{"amount":"+0.8494773507118225","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":"Q540059$D213458C-2A67-4376-A364-464A5CBF2813","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Counting triangulations of planar point sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Counting_triangulations_of_planar_point_sets"}}}}}