{"entities":{"Q1189285":{"pageid":1200034,"ns":120,"title":"Item:Q1189285","lastrevid":46291992,"modified":"2025-12-24T12:17:45Z","type":"item","id":"Q1189285","labels":{"en":{"language":"en","value":"Polygon triangulation in \\(O(n\\log{}\\log{}n)\\) time with simple data structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 54912"}},"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":"Q1189285$50E2FC14-4898-4CF2-9FCC-8FFB878EBC72","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eeb1bad682effb93b9b68cff7ac02d15dc34c10d","datavalue":{"value":{"text":"Polygon triangulation in \\(O(n\\log{}\\log{}n)\\) time with simple data structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1189285$62819DDD-C31C-41EE-8AC0-D428EBF48911","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"88c747638122f5b6f610da2c9276a309c80071e2","datavalue":{"value":"0753.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1189285$7A0C4A87-7877-4016-8456-AFCD55995BF8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b843e0fd44091ed82b97bb1a006dd603936d5ae7","datavalue":{"value":"10.1007/BF02187846","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1189285$4E074BC9-6943-43DB-A475-4A2A1F518DDA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a25d6c9ed2c7d3c838dcd849030b5593bce4a77","datavalue":{"value":{"entity-type":"item","numeric-id":1058850,"id":"Q1058850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$553571E2-FEA6-4C36-BCF6-B84664E63D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"36ae842d0db299f2f5b4c98a42bd381e6c19478d","datavalue":{"value":{"entity-type":"item","numeric-id":489752,"id":"Q489752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$080C16BF-CDE2-4395-BFB9-ACFAF274C0D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"065c91f208b67eb2296cd8ea5272c33efd202f25","datavalue":{"value":{"entity-type":"item","numeric-id":598808,"id":"Q598808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$1B2F44BF-631B-4256-8F40-8C5FEB59BCA4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$7FFB80AF-8077-4538-A625-412D8B0DC3CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9b40ce89936be2de8343a01d1ced7ff59f76b3e","datavalue":{"value":{"time":"+1992-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1189285$F7309946-5760-4BC6-9EDC-64DC2D21F41C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc22f71bff885a2bb0a8cd74c0274602356e7e6f","datavalue":{"value":"https://eudml.org/doc/131199","type":"string"},"datatype":"url"},"type":"statement","id":"Q1189285$8A923C6B-8809-4A93-AEFB-12D067C5CCE2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b2c4de76d7d7919d680b1d6f5c1a784da8eb96b","datavalue":{"value":"An \\(O(n\\log\\log n)\\) time algorithm for triangulating simple \\(n\\)-vertex polygons is presented. The rasterized version of the algorithm even consumes \\(O(n\\log^* n)\\) time. Comparing to optimal linear time triangulating algorithms due to \\textit{B. Chazelle} [Discrete Comput. Geom 6(5), 485-524 (1991)] the underlying data structures and procedures are quite simple. The algorithm is based on the balanced horizontal visibility partition of a given polygon.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1189285$563F68CC-0428-4B85-844E-4C000F20A448","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1189285$9DF916AA-D05B-4841-BD5C-BABC7ABD7079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1189285$85E6823D-33D7-493A-8363-44F9A5B72778","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b27b856d096ec73f3a384ed446b02f7ab644d27","datavalue":{"value":"54912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1189285$F102A4D0-1388-4A9D-9B04-BDAEDF471A07","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd3b97137fc5cddeb53bb49b8b441b42d47d65a","datavalue":{"value":"triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1189285$8DF414E5-5C89-46A4-8FDE-94407BE645F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed28385b5c62eaaf3b0756eb74715fae1afa8293","datavalue":{"value":"simple polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1189285$3F15F3C9-E80C-4071-B05D-5D3A3C80A640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03daccd06752542c20c75bcb71c48134a948fc91","datavalue":{"value":"horizontal visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1189285$2E713AB3-ADC7-4ACE-83D6-182C94B82A1F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$22BF4925-F4E6-4231-8B48-39A729F70C6B","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":"Q1189285$A2AAA719-EDD0-43D4-9BCF-6EE08ACA5C10","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e4f93a48928859c6601c7fed9096cb4a04356fd3","datavalue":{"value":"Q56389442","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1189285$EA74EF16-8150-4431-ADB4-D1CAE5F84F49","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1527977d1e97f551ee80e9595c567d4fb5b3ce20","datavalue":{"value":{"entity-type":"item","numeric-id":1176324,"id":"Q1176324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$CE15216D-2302-4672-A8AE-BC54D328A3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14bb5de49d1025f33147045f216b73559caa6b2","datavalue":{"value":{"entity-type":"item","numeric-id":3721846,"id":"Q3721846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$CC2F535D-47F5-4729-8F75-70205796C4F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edb11b0dca7253830be5f8139bd13817d5fa1992","datavalue":{"value":{"entity-type":"item","numeric-id":1823686,"id":"Q1823686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$FE9502BE-14A8-444D-8591-AAE35880DF18","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":"Q1189285$165B9515-F25D-4FF0-8A2A-FF97D5C0B0D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f0a1a2b9bf668daa897de5ce6a3be86456a7969","datavalue":{"value":{"entity-type":"item","numeric-id":3721847,"id":"Q3721847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$EA02B608-3735-47E3-B543-8B085FC3BB61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8b4714c779b60dd81191c02fce72803a9318c6e","datavalue":{"value":{"entity-type":"item","numeric-id":911762,"id":"Q911762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$91402880-BB1A-4670-9867-15070C605D62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae0713540eb691df7bd8820bc004fcb597f484c","datavalue":{"value":{"entity-type":"item","numeric-id":1249042,"id":"Q1249042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$C0B7EC91-967B-46F9-9D47-3477F00DB8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2c6b273bbbfb23a71b64948d50760d60883087e","datavalue":{"value":{"entity-type":"item","numeric-id":1101226,"id":"Q1101226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$25B955EB-6538-48C2-BCCB-CB9BF5F2DEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b12fa80e0883c7916ad7ebd37bad50bd07b508","datavalue":{"value":{"entity-type":"item","numeric-id":3670558,"id":"Q3670558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$DCDDAFCE-D14C-4178-9161-058578E0E071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b4f81716b6b99b3385ea9ee884bdf2887fe5b7","datavalue":{"value":{"entity-type":"item","numeric-id":4721658,"id":"Q4721658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$CCB366E5-080D-4A1B-A68D-0BA0855D9852","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":"Q1189285$36868BC5-6FC0-47B4-820C-8537BA155CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac6746c85a669097b515fb2d37dce6f94b8ec7c0","datavalue":{"value":{"entity-type":"item","numeric-id":3777450,"id":"Q3777450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$D04C3870-7E77-475F-BB03-C409D5E48655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03e6a793829a78cf1632745f6762bdcf4eae7af6","datavalue":{"value":{"entity-type":"item","numeric-id":4040234,"id":"Q4040234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1189285$1A76E2AE-B4CE-4F5B-B2F5-8A1F5729DD46","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"4fa350d31f0261960d5b29eabcfaabc08e2867e1","datavalue":{"value":"journals/dcg/KirkpatrickKT92","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1189285$C3B3E832-C18A-49EC-808B-87B4228F900E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ccd087bcc69ff4b38aaa13c81d6c63b2a517665","datavalue":{"value":{"entity-type":"item","numeric-id":3777450,"id":"Q3777450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95ebe6bb03f3cd8f5d48afc77e1e66505ada7b1d","datavalue":{"value":{"amount":"+0.921295404434204","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":"Q1189285$B6EF74D4-229A-4C26-AB6B-493B9C655A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01aae63e382b88c58f0a5487b6b0cae3b93a4aec","datavalue":{"value":{"entity-type":"item","numeric-id":1176324,"id":"Q1176324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a36c8170e67809f6c1d018d798f65ba98222b62","datavalue":{"value":{"amount":"+0.8741886615753174","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":"Q1189285$292EAFB8-5CC2-419C-8AC1-DE436E342310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7df7e1a6dacf38d69f52326f7b280c20f4dc4f16","datavalue":{"value":{"entity-type":"item","numeric-id":3721847,"id":"Q3721847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae57d8673aa738de4ee0c5113f10e5d1336b9506","datavalue":{"value":{"amount":"+0.8542612195014954","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":"Q1189285$9BE25F4F-4D7A-4EF8-A55E-EA36FEAA266C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57d75ee02a28b62542a0e0e89b7c3f0058e6cf5","datavalue":{"value":{"entity-type":"item","numeric-id":3721846,"id":"Q3721846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19639745560a23bd4549846a1d19e82635a27ad9","datavalue":{"value":{"amount":"+0.8458836674690247","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":"Q1189285$EAD798F5-486C-453B-8D90-15A847CC04C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d420852bb62fc90aaab8b17b700844ecc123943","datavalue":{"value":{"entity-type":"item","numeric-id":5946382,"id":"Q5946382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b74b46e6aae9ff35d413fc7aa3edfc509ed3792","datavalue":{"value":{"amount":"+0.8367927074432373","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":"Q1189285$91D32282-8749-4CE2-9409-8F94BA3F9467","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1189285","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1189285"}}}}}