{"entities":{"Q911267":{"pageid":913115,"ns":120,"title":"Item:Q911267","lastrevid":65290278,"modified":"2026-04-12T01:34:20Z","type":"item","id":"Q911267","labels":{"en":{"language":"en","value":"A linear-time algorithm for computing the Voronoi diagram of a convex polygon"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4141486"}},"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":"Q911267$54643F31-278D-496A-9F77-8F96D1B0C388","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"541ac4d2fed0dd84d0e19a2da865e9677a9c84c1","datavalue":{"value":{"text":"A linear-time algorithm for computing the Voronoi diagram of a convex polygon","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q911267$1715FEF3-81F7-4DFF-B2FF-496222D53285","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae65995017696aee86d1949dd87fe8167f8afd50","datavalue":{"value":"0696.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$673D97F6-2F9E-4F05-8828-B56E8FEDF2E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"256a9d43719a79f472f14353507a0363170b92b2","datavalue":{"value":"10.1007/BF02187749","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$7357D4E6-6858-47B2-BBA5-0D2DBA5A98BD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"64a5e02458a327e7b854a0a51ea17759c9e5c450","datavalue":{"value":{"entity-type":"item","numeric-id":834913,"id":"Q834913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$35CAF3D5-81FA-4576-B411-D59E6919C949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27055c7a0af767b1f36b14e7674bc0aa2224fdc0","datavalue":{"value":{"entity-type":"item","numeric-id":534491,"id":"Q534491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$BABBD48C-B240-4703-A970-DB5BB1287FC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c19976f280af2a9432c2c51239959366e237e59c","datavalue":{"value":{"entity-type":"item","numeric-id":598817,"id":"Q598817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$CEE4A7E6-8F5C-49AB-9FA9-D8793D876C84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81778509c7c34d1a374c80a7a64e0dd6e1cd7f8","datavalue":{"value":{"entity-type":"item","numeric-id":701710,"id":"Q701710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$C6500E49-E788-4499-8C96-8B9F01CBE724","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":"Q911267$49DF0C71-EFBB-4456-9ED9-F6B4D6438DC7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q911267$2809E13B-B276-4D81-A2EA-2B4076B291E1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5abe9551bfc647134c2d3844b56bf3c94c7bf5f8","datavalue":{"value":"https://eudml.org/doc/131098","type":"string"},"datatype":"url"},"type":"statement","id":"Q911267$609D16F7-F2FC-4CC8-A5A9-644B83F9B98B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7941d7f29a7fd77cb3eba5d19fcdbab21f65ab04","datavalue":{"value":"The main result of the paper is a linear-time algorithm for the problem of constructing the convex hull of a set of n points in three dimensions whose projections on the xy plane form the (counterclockwise ordered) set of vertices of a convex polygon.    As consequences, linear time algorithms are obtained for computing the Voronoi diagram and the furthest-point Voronoi diagram for a convex polyon vertex set, for updating the Voronoi diagram after deletion of a point site, for constructing the medial axis of a convex polygon, for finding the largest inscribed circle and the largest empty circle centered inside a convex polygon. These results are also used to obtain better time bounds for some algorithms for proximity-related problems. Some open problems are posed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q911267$51C8D54E-4134-4500-8FC5-26EC0DCED414","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"257d0165052e5019ac8fd49a93c7aebbdcc243c0","datavalue":{"value":{"entity-type":"item","numeric-id":751866,"id":"Q751866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$C6060B8E-1D5A-445C-AA88-8B83C0426D68","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$A2A7F37D-2AD3-42C6-A8CC-CD678AD58DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$6A2345E2-C0CB-49D9-B51F-1AB4CD5B41EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$410DD7EA-6862-4B09-9B3D-28C90CABC2DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eacb4c12e7e48991b8c7d74dfa28473bc9ec7a41","datavalue":{"value":"52A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$EFB4C425-9B4F-4CE5-922D-FA2C825E49A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"baad6c8e87587c7e65368ac76c67ce0f2bd1e65d","datavalue":{"value":"4141486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$7EC97029-9136-411E-9A6E-E40EC9DC6975","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q911267$FAD06802-EC13-48C7-BF1C-E179617FF193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7638652825683bfe9fbdcacf89d6fa0bde32cc7a","datavalue":{"value":"convex polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q911267$EFF2A7B7-54F7-496F-B325-A825A6A2C2DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q911267$4D24BF30-1781-455A-8B4D-84250981934F","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":"Q911267$2EEA3267-0195-4722-96F9-3D5279EDCB93","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff4e812fbcc008a1d5259e712cd9203d973f596","datavalue":{"value":{"entity-type":"item","numeric-id":3711764,"id":"Q3711764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$46D8B1A6-476F-4C48-BD00-9E3014140AF2","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":"Q911267$2374DEF7-09E6-4790-BEBB-778388E65E52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86bd27ab57f23d3defbb32a5ccb58822295dd2e8","datavalue":{"value":{"entity-type":"item","numeric-id":3953183,"id":"Q3953183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$81A0C62F-D161-4ACF-B575-1D20C3D023C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cceec15e0bf6f1544f3e1864012ec31a05ee6eb","datavalue":{"value":{"entity-type":"item","numeric-id":1078807,"id":"Q1078807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$223C3F3F-B694-4767-A2B1-B36647980629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e583938929e7d2c63f5f6d8fed7581a322ce98a","datavalue":{"value":{"entity-type":"item","numeric-id":1134524,"id":"Q1134524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$FB1E3FFF-40BE-4C04-ABCA-59E3D79522FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae4f8c5ae7e617e50720f3371cc8ed313a02d5d4","datavalue":{"value":{"entity-type":"item","numeric-id":4134504,"id":"Q4134504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$D6D0769D-CB6F-45F6-8D23-9538AC1D5DC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911267$3060376F-5BA6-4332-B39F-83DA252847F6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"61458fc8f6c0726bb229079723270727129afdcb","datavalue":{"value":"W2074863496","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911267$1B7ED4AD-690A-46FD-8470-D8E4A30A4771","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"627af6a06a5c8627bd0cf706405f194148c0a839","datavalue":{"value":{"entity-type":"item","numeric-id":3787490,"id":"Q3787490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7c385225412fe653888867d2774b4b6bbe0ffbe","datavalue":{"value":{"amount":"+0.8314831852912903","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":"Q911267$412C5656-C0A8-49E5-991E-760CF0BD618D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6346566eb826f1274e388af11529ad0f5a97da6","datavalue":{"value":{"entity-type":"item","numeric-id":1269914,"id":"Q1269914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d18c6efb3d974a92fe1f5d76e1ccfbfd338b31c4","datavalue":{"value":{"amount":"+0.8210094571113586","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":"Q911267$634379A5-A256-4764-A27D-1BF01F9344D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fffc3167dc5962df5ece76127d5a5cb3a0b6abd","datavalue":{"value":{"entity-type":"item","numeric-id":5056167,"id":"Q5056167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"642f86b990d403eccf3c41a75b131d009ec95401","datavalue":{"value":{"amount":"+0.8191558718681335","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":"Q911267$8FE8DEA4-F966-4CA3-B6B6-3A248E68880B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78a84bb46311deb3fbdc13c2704f633fcda917a0","datavalue":{"value":{"entity-type":"item","numeric-id":4037407,"id":"Q4037407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3467073c184573bf0dfe346984b1299b966ee4e5","datavalue":{"value":{"amount":"+0.805577278137207","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":"Q911267$DBF9E744-B438-426C-BA02-5D1D4F5F6481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eae0d953bc2f6459a8a757099409c7d19a7bfacd","datavalue":{"value":{"entity-type":"item","numeric-id":5687650,"id":"Q5687650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea1b31ce896974ab02cccda72f5776459eeecfd3","datavalue":{"value":{"amount":"+0.8044418692588806","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":"Q911267$A28155FF-D645-4B10-874A-62B2F738C264","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear-time algorithm for computing the Voronoi diagram of a convex polygon","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear-time_algorithm_for_computing_the_Voronoi_diagram_of_a_convex_polygon"}}}}}