{"entities":{"Q582095":{"pageid":583862,"ns":120,"title":"Item:Q582095","lastrevid":62948685,"modified":"2026-04-11T09:11:14Z","type":"item","id":"Q582095","labels":{"en":{"language":"en","value":"Finding the upper envelope of n line segments in O(n log n) time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4130010"}},"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":"Q582095$B959B799-CC1E-44C0-8499-360EDC8C95A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5afcd5f414fbba3c3b5407ec8aa5e095efe1a6dd","datavalue":{"value":{"text":"Finding the upper envelope of n line segments in O(n log n) time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582095$A39C1116-7683-4514-819E-4A863E5A4E69","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"697264c76b07a9b595cef9a5d06a7e2c9465f6d7","datavalue":{"value":"0689.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582095$F8AF7003-1260-463E-875D-C6205F7955EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a21c74cb268ab1a43fbb4e9f83e2f4224c5bbf6","datavalue":{"value":"10.1016/0020-0190(89)90136-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582095$4EDBF819-1394-4245-BCED-C7D5037F3421","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":"Q582095$67CB5B66-661D-45AE-AD26-7C88E50EE537","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":"Q582095$06EC6667-5200-4238-B56C-13B0F5623ECC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582095$E638AE62-41E4-4BC6-A527-466C79447381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582095$D134226A-FAB1-47E3-AD75-DB42C7BFE2D8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3789dfc64a60862028048ec5fef73bdc68154787","datavalue":{"value":"4130010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582095$2CE172A0-7D87-41A5-8757-3F2821DF1738","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q582095$B35CA520-3BED-4AEE-8F2E-8E0C2D46E718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05993620bbf4808db33cc921ace29c30f333dd5e","datavalue":{"value":"upper envelope","type":"string"},"datatype":"string"},"type":"statement","id":"Q582095$6A1ACEF6-4725-4DE6-BBE2-10C13E39EEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8ecb9ba39ffdb1ea2c5ee33c86530ae7c9cba72","datavalue":{"value":"Davenport-Schinzel sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q582095$04594EAD-20A5-4D20-B41C-EF1E5D0A1AF1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"94eab6fdb0a0437dc92c234ddacb5446e0f8992e","datavalue":{"value":{"entity-type":"item","numeric-id":1384195,"id":"Q1384195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$6A740F9D-02EC-443F-B1D0-48F2F13A67C3","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":"Q582095$21073EAD-6ABC-4C5B-B882-6CF3C9B5ADC9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"93e8ff82413360e1cfb4cd888211930e10b2814a","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90136-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q582095$253C0AEC-FAC9-4BA1-86DB-36F6A8DB3E23","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4f640e2abba945963d73e3b6671d500316a7cd6f","datavalue":{"value":"W2020590137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582095$A878FDED-C6F2-4747-90A9-585CD4C5CC95","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ad6a447ed415489e99550ada5d106e44638f0b1","datavalue":{"value":{"entity-type":"item","numeric-id":911595,"id":"Q911595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$25E85204-53DB-4230-8D3E-56762F0FBD49","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":"Q582095$A6AD9E67-8D10-4839-8469-D08207DEF86D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a576cd28ada66a4d90fff61b4f2556c5be21d817","datavalue":{"value":{"entity-type":"item","numeric-id":1071526,"id":"Q1071526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$AF0E0DB6-7574-4364-A659-35D1A031ED45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba9e98d83fb097641689563c120aebf958873f5","datavalue":{"value":{"entity-type":"item","numeric-id":3796769,"id":"Q3796769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$ECD8BFDD-5B91-4243-9016-4201237E66F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a242496d908b6d1e30e137bd48db323e9a6e17e","datavalue":{"value":{"entity-type":"item","numeric-id":5340927,"id":"Q5340927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$08FCF24D-46B1-42DC-A1A2-8D2136FA7223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05e150681c1d0241ecb463ace4c088cbd7d131cd","datavalue":{"value":{"entity-type":"item","numeric-id":3319776,"id":"Q3319776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$17FAB6AE-DBCC-48A2-AD48-D1ADB17E36DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c368a550cf5b4e92a6d4f0e58d9ca1eb20b223cd","datavalue":{"value":{"entity-type":"item","numeric-id":1097884,"id":"Q1097884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$90EBDF93-10D8-4CDF-BF03-01732B04E737","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":"Q582095$EE54CB14-95EE-453E-8780-3F52F47E9440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06b820d7730c4483ffdeaf5f1bb9567aad23b088","datavalue":{"value":{"entity-type":"item","numeric-id":3906428,"id":"Q3906428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$8DB4FC06-D932-4A28-851E-851389D6BE0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dd1104c3819dc61bbacb583d9a9ffa28e54bb09","datavalue":{"value":{"entity-type":"item","numeric-id":1098294,"id":"Q1098294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582095$F3B5C94E-C9D9-44AA-954D-41C2AC76D7A6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c823ef066da1f7d2aaf88434a06943ca47b6a9d1","datavalue":{"value":"Q29302733","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582095$69DCC69A-BFF7-4C2C-8211-979B309A3D13","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a4f202cadadce3861abdcc9e2900e01fc87c488","datavalue":{"value":{"entity-type":"item","numeric-id":5056118,"id":"Q5056118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d33e7da842805f29f648b81743a1e114408cbad8","datavalue":{"value":{"amount":"+0.8640847206115723","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":"Q582095$373CA2FB-CC47-48DF-ABA7-25DEB7A26779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c14dd5e9af45a966cedc38993d0e8e86b411b010","datavalue":{"value":{"entity-type":"item","numeric-id":1199830,"id":"Q1199830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c04346bfbb67d66d1d8a0e6f63868b3c3510b32","datavalue":{"value":{"amount":"+0.8504348993301392","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":"Q582095$475F4E16-4835-4A3F-A0E9-BE85A1557018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c9571bfab1e8b921d5e06b2b76e9df94811bd25","datavalue":{"value":{"entity-type":"item","numeric-id":1338960,"id":"Q1338960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c05818fda64b36b9e2f5c3cb4d4cfa1fb1a4f1f0","datavalue":{"value":{"amount":"+0.8501701354980469","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":"Q582095$02A387A3-9855-4D3B-B906-56718C627C14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"090f5802f2be4d20920ca9a37abda72c5d071bbf","datavalue":{"value":{"entity-type":"item","numeric-id":919830,"id":"Q919830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67c2fce715ce5a04a29df3fd5f06fc805b82a184","datavalue":{"value":{"amount":"+0.832261323928833","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":"Q582095$0EA2EE28-F104-462F-A18F-6A33E45D114F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a6637298270e4a319b07980d1b09b7722aaaac7","datavalue":{"value":{"entity-type":"item","numeric-id":919829,"id":"Q919829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b630f28cc3e53a21769520ce8e6da03a25eb5170","datavalue":{"value":{"amount":"+0.8247315883636475","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":"Q582095$70CF692A-A6F7-45D8-97E5-EF8867B3DF12","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding the upper envelope of n line segments in O(n log n) time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_the_upper_envelope_of_n_line_segments_in_O(n_log_n)_time"}}}}}