{"entities":{"Q1262133":{"pageid":1272883,"ns":120,"title":"Item:Q1262133","lastrevid":49327024,"modified":"2026-01-06T23:31:56Z","type":"item","id":"Q1262133","labels":{"en":{"language":"en","value":"A fast algorithm for computing sparse visibility graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4123307"}},"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":"Q1262133$AC9B008D-EA37-42C5-83C5-FB385313C2C6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"00e250f50c16341e2c5b4940aa2ef6756b9608d3","datavalue":{"value":{"text":"A fast algorithm for computing sparse visibility graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1262133$2F32C09C-D571-4B98-BC3B-D45A847C1437","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2650f4838f6a242e9abc517ce5e6b1e0cb871770","datavalue":{"value":"0685.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$FFB941F2-FEED-41A0-BDAB-2AB2665C3280","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c07cd6fe7babb6c1316018515e86074db958841f","datavalue":{"value":"10.1007/BF01840385","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$1858579B-4411-45B3-8B77-3F1201B51A8D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb1fe506bdc16b691b71530030d72978968d6680","datavalue":{"value":{"entity-type":"item","numeric-id":1127533,"id":"Q1127533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262133$9B36237A-55A0-416B-8F3D-CD95F536D855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e52a12d90ca5312fef7acb3a90e1100b17ed79f","datavalue":{"value":{"entity-type":"item","numeric-id":189690,"id":"Q189690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262133$A3147FF4-F400-4D5F-82F7-60A9EC9A5E4F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262133$6D2E8989-4F70-4E7A-BA39-7D4B529BE0C4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q1262133$8A17683B-7C10-4860-856E-ACB7D6895C57","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6febb27619589629c4c6dcce7cb56ce43a2da6b","datavalue":{"value":"The authors present an O(\\(| E| \\log^ 2n)\\)-time algorithm for constructing the visibility graph of a set of n nonintersecting line segments. Here \\(| E|\\) stands for the number of edges in the visibility graph. The algorithm may be inefficient for dense visibility graphs but it is faster than some previously published algorithms [\\textit{E. Welzl}, Inf. Process. Lett. 20, 167-171 (1985; Zbl 0573.68036) and \\textit{T. Asano}, \\textit{L. Guibas}, \\textit{J. Hershberger} and \\textit{H. Imai}, Algoritmica 1, 49-63 (1986; Zbl 0611.68062)] on sparse visibility graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262133$C69334CA-8C54-4994-AA6C-E577F713F271","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$9E9D8348-5C4F-4D4C-9CEF-EE24B8232C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$0A144BE9-D224-4000-893B-DAF8D480E3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0406717a08583a96c32ef01fc47248ffad00fc6f","datavalue":{"value":"52A30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$DB6E21FE-A46F-4FF1-BD3F-C7283B313C90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$FFD786C8-FB75-413E-B25D-C5B0B3893C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5ae9e2988e76d371f7e87b79bcd004ea2b80f64","datavalue":{"value":"51M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$20E6B604-D2EF-4B3B-A0D3-FBCC4890E4C6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68ac53d2a9e91b275bf005a0103f56f45e27819c","datavalue":{"value":"4123307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$13A46932-345D-4CC5-AC2A-2C5215616C3A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262133$79482325-3743-4D89-AED1-3D371C80BA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb2624169a49c8ac0f44121c56e48b90d16e867e","datavalue":{"value":"visibility graph construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262133$C13E9F28-6CCB-4DA6-8609-BBE5C89A1C68","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1ba4a6e46d39a41518db65f4f97cbfd2a0693778","datavalue":{"value":{"entity-type":"item","numeric-id":238069,"id":"Q238069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262133$C1F097F6-6255-4CA7-B632-2D3F40C74983","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":"Q1262133$5CCC00CA-4992-4863-8F0E-A2B70C2634E7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262133$8B0073B3-73D7-47BF-875B-305E331805DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa1ba3f58e2231825bfce74b74cabb3c6d2ddd9e","datavalue":{"value":{"entity-type":"item","numeric-id":1087340,"id":"Q1087340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262133$E395F2F7-2B56-4C37-83BF-AED7D393E45F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a715219fd6274692c890d4aa82ed20d1406419","datavalue":{"value":{"entity-type":"item","numeric-id":1158972,"id":"Q1158972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262133$BC695B40-5A34-41C4-B7F2-EE03FB7022C6","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":"Q1262133$F04B6CF1-23F4-4C95-9415-6A74EE1394D4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa9edcbf84b8684eef1268892e54fe5807fb37f3","datavalue":{"value":"https://doi.org/10.1007/bf01840385","type":"string"},"datatype":"url"},"type":"statement","id":"Q1262133$55527F44-D5BA-4CBB-A899-6F7260964FFB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a817fe72b0b937500c52220606a30aac90d21042","datavalue":{"value":"W2067947381","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262133$8BE7F373-EE6C-4540-A9C2-381B8671F1CF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e562f60f179c471530b9637dfacebdfa5bb04ba9","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a732f463268917ede036ae49d9dde18bc6675bf","datavalue":{"value":{"amount":"+0.8731663227081299","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":"Q1262133$7FC90E57-E31A-4334-A5ED-AD709AD0F477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"600e2ffbb3bfe3a0c6bac2c9da37af3171281659","datavalue":{"value":{"entity-type":"item","numeric-id":1098639,"id":"Q1098639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5f1916b7a6e9e9a3a695c3f822a2cc259cda573","datavalue":{"value":{"amount":"+0.8398227691650391","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":"Q1262133$2DCE2588-C41E-40D5-AFBC-3A2B36A92E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4885949607118bf7e8e0d5b3d2684645e928f4a","datavalue":{"value":{"entity-type":"item","numeric-id":1198072,"id":"Q1198072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1fc99369f13d20da9c04f5fba7b6e955d743115","datavalue":{"value":{"amount":"+0.8380387425422668","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":"Q1262133$CE673B3B-E461-4F03-84FC-573D5AFB2A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e112832efca1b7ffd98ab0695766e8cbec48871","datavalue":{"value":{"entity-type":"item","numeric-id":4326861,"id":"Q4326861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03d61440ad11de52df90848a4967a99bf540f296","datavalue":{"value":{"amount":"+0.8284128904342651","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":"Q1262133$04926D54-FC6B-44D1-A7E9-F6E6C5011509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dce5333f31b8cffedb63367869f40b55a8f08a0","datavalue":{"value":{"entity-type":"item","numeric-id":4037439,"id":"Q4037439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae122aa57863e5fb3dee2654471931d3f20fa827","datavalue":{"value":{"amount":"+0.8153285980224609","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":"Q1262133$BDF3924A-D464-4BAD-8326-785FC41FD0BD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1262133","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1262133"}}}}}