{"entities":{"Q753493":{"pageid":755342,"ns":120,"title":"Item:Q753493","lastrevid":64118397,"modified":"2026-04-11T17:46:12Z","type":"item","id":"Q753493","labels":{"en":{"language":"en","value":"Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4180798"}},"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":"Q753493$DAE1BDB5-8A72-4D06-81F8-4343D29250A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e44e1824360b81b2619d1eaca2d0213b60d828e1","datavalue":{"value":{"text":"Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q753493$D55D978D-68FE-414D-A904-174A17C76892","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"89f63fc008399eb1dbe18e462d64a4e587290b88","datavalue":{"value":"0716.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753493$2F7D85F6-4383-4A91-89F0-C70D2872B74E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"16c0fe7101165b45893d011c79c3230acc611d24","datavalue":{"value":"10.1016/0020-0190(90)90104-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753493$5EA32C49-E912-44A1-B46C-4A43FB29C707","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"547a70f32038f5698afdc474eeef7f9e925fba61","datavalue":{"value":{"entity-type":"item","numeric-id":699184,"id":"Q699184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$B790D54F-064F-4AA4-8D47-0FC2F9C5DE81","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$96C1AD9E-D9CB-4264-80F4-4538878F3B97","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":"Q753493$DAE8C413-2214-467B-B56F-7AE00DA28DAF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"def784f36b5c0197bc931fe12271733822031db1","datavalue":{"value":"In the computational geometry literature many algorithms are described in a high-level way, in that certain elementary operations like e.g. computing the (first) point of intersection of two curves, are assumed to be available at constant cost. While this point of view is acceptable in linear geometry it is incomplete if objects of higher algebraic degree must be processed.    This problem is addressed in the present paper. The authors provide a useful survey on the complexity of oracle operations that occur in computing convex hulls and Voronoi diagrams of higher degree objects.","type":"string"},"datatype":"string"},"type":"statement","id":"Q753493$7A79D5D9-69D2-4C0D-BDE2-221E7B45C03C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753493$62BAA64B-C969-4291-AF5C-381485E012E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0d8912a48ac60770db1c80088e9517c70dd683cc","datavalue":{"value":"51-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753493$4FEABF64-A012-476B-B905-1919C7DDB4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753493$4A2EEAD2-C51F-4F04-9414-8EFE2E05657F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ae6d255fee623e98dce895cc9591201852bd5ab","datavalue":{"value":"4180798","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753493$5B452CC2-A749-4D93-B0AA-36A0E044D39D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q753493$57C22437-03FA-47C9-A877-D722D050037D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d17f81be13db0c98109a613556f3d5912f5e3240","datavalue":{"value":"oracle complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q753493$03543832-10A0-43F1-B907-59FBE05EE3EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87b147aa16e08aea71594b690e239b8aa358d8be","datavalue":{"value":"convex hulls","type":"string"},"datatype":"string"},"type":"statement","id":"Q753493$A822F9C7-5485-4A7F-BE22-28B7E6BA5DAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2a942004e7c3ebf174ed889f18fd8e1f8b9b24b","datavalue":{"value":"Voronoi diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q753493$D33099A1-3B69-4AAD-A68E-1035D9F120D4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d10d7094195fd93795d0560abee20f8cd8844524","datavalue":{"value":{"entity-type":"item","numeric-id":166235,"id":"Q166235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$B4F8C099-E8F6-4C77-AB63-A4095FFD8970","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":"Q753493$3437C296-DE74-4608-986E-6C4340606B45","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6b28015bb13a0b2f3838f6df74c3dcc2848326a9","datavalue":{"value":"https://doi.org/10.1016/0020-0190(90)90104-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q753493$E6E48BE7-5955-4FF5-B650-31F4576C2B85","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8d0ad27794e73f0f7ba39849e47321c04e57ec75","datavalue":{"value":"W2034187229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753493$5A2F3459-4519-4003-BF5B-4A41D3BFF1E5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"35e0dae2037115e9c3816d90294d9e5abd9ba334","datavalue":{"value":{"entity-type":"item","numeric-id":5633585,"id":"Q5633585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$D33E896B-D26D-4D2D-9497-D35D46DBAE74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99114b1bd38a031039ee6a9bed0217048b0b5658","datavalue":{"value":{"entity-type":"item","numeric-id":1101224,"id":"Q1101224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$4B896159-E659-4B8D-8E12-38396B5A4FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be7bad0b0921be8518e73946a7a05c664af575a4","datavalue":{"value":{"entity-type":"item","numeric-id":3783564,"id":"Q3783564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$80551DA2-F248-4736-A300-1BEE5774DF8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8332468c56cf425ddf859080eb3b69a9207db47c","datavalue":{"value":{"entity-type":"item","numeric-id":760006,"id":"Q760006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$90EA898B-4479-4FC7-A5D4-364899D08859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b8884c39b26a1b7cbe9eceef9f26bccd675df0b","datavalue":{"value":{"entity-type":"item","numeric-id":5795154,"id":"Q5795154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$0D364150-1ECF-43B8-8C7F-ED5AB99D0665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b2d4c35681c657135b1459d72a927361adde702","datavalue":{"value":{"entity-type":"item","numeric-id":1093370,"id":"Q1093370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753493$E421067C-9D90-4509-BF25-900DD2D2B221","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1aa7314afcd5d817b41efddef2bdfa3d48590157","datavalue":{"value":{"entity-type":"item","numeric-id":4797580,"id":"Q4797580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bac7fcc7794735890029c076bab1828bd390f8a1","datavalue":{"value":{"amount":"+0.759267270565033","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":"Q753493$CAA530E8-0E3F-4984-B051-78022997993F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9c90de8ecea0b6a750ab61d8be00eabb80de99b","datavalue":{"value":{"entity-type":"item","numeric-id":4845369,"id":"Q4845369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bce9240ef31d4191c32e04772a54b23ab450e65c","datavalue":{"value":{"amount":"+0.7499346733093262","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":"Q753493$C01957BA-2F7C-4393-B2F8-7926BD46A423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddacf873edf38184346fe037a8cc37b648dacded","datavalue":{"value":{"entity-type":"item","numeric-id":3479543,"id":"Q3479543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ad30e7392a6545f12db737987dcd26009a6c33f","datavalue":{"value":{"amount":"+0.7495734691619873","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":"Q753493$A085405D-A443-432A-880D-4E4D3B61648D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d1b6b44e8d4f804377fcb3826a8dc54b3395853","datavalue":{"value":{"entity-type":"item","numeric-id":3776623,"id":"Q3776623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b87e6088d78b27c55575a6251c6dafd56e97740","datavalue":{"value":{"amount":"+0.737061619758606","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":"Q753493$D80E5BCB-92DB-4EB6-8482-D47A2CF4E941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a30a9e77e2546a1c4dfd9ca0e42c73b8b46fcead","datavalue":{"value":{"entity-type":"item","numeric-id":691570,"id":"Q691570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baf33dfa12c0220f18ea6643871e8b2529cb31ce","datavalue":{"value":{"amount":"+0.7353221774101257","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":"Q753493$4DF60A4A-F37A-4B1D-B578-DC7B871AB521","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Oracle_complexities_for_computional_geometry_of_semi-algebraic_sets_and_voronoi_diagrams"}}}}}