{"entities":{"Q919830":{"pageid":921678,"ns":120,"title":"Item:Q919830","lastrevid":49412074,"modified":"2026-01-07T03:01:21Z","type":"item","id":"Q919830","labels":{"en":{"language":"en","value":"The upper envelope of piecewise linear functions: Algorithms and applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4162270"}},"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":"Q919830$9F8240DA-052C-4886-8699-9916D7BBA576","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7a918c27f76112a652ffedf20a41c9625796fd80","datavalue":{"value":{"text":"The upper envelope of piecewise linear functions: Algorithms and applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q919830$0D1D924D-B460-4563-B1B9-87B24A1DD4B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1df37249724b945d86965afee39c898d6764991f","datavalue":{"value":"0707.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919830$DC92CD13-EC9F-4B45-9358-F2DC585676BE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f90ac2e65652050804d2c593c77b7ab6cc86a5f5","datavalue":{"value":"10.1007/BF02187733","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919830$3E596BA9-6768-4EF6-A637-0DC1C1A71D2D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a06f7d76e1dbfa89a80e5d40561052d9e137ca58","datavalue":{"value":{"entity-type":"item","numeric-id":242843,"id":"Q242843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$D1DF68F1-D765-4310-834E-AAE8F5263866","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":"Q919830$415C061F-4C27-4098-9338-305558403E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05973d4747711a904c4eb354f325fda834906623","datavalue":{"value":{"entity-type":"item","numeric-id":396765,"id":"Q396765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$DFC72E8B-874E-48E6-9BEA-9A724D8B8441","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":"Q919830$300254F1-20DC-4F8B-8D18-C86D8F5A6665","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":"Q919830$14A561CB-EB09-4771-B22A-9B5050EC4A2D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c364371fdfb8e2a0bb9fd2c7f584e6f1de158772","datavalue":{"value":"https://eudml.org/doc/131082","type":"string"},"datatype":"url"},"type":"statement","id":"Q919830$CFAD3A2A-EAEC-4BE8-9DAB-6308DD1C2FD9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"327a429fff2094fbd09e96a1a8e73975e8a281bb","datavalue":{"value":"This article is devoted to the combinatorial complexity of the upper envelope of piecewise linear functions and its consequences to various problems in computational geometry. The upper envelope of the system of functions is defined as its pointwise maximum. In the case of linear functions the envelope form a cell complex. The complexity of the complex is the number of its faces.    An algorithm is presented for finding the upper envelope of n linear functions defined in the space \\(R^ 3\\). The algorithm is asymptotically optimal and its time complexity is \\(O(n^ 2\\alpha (n))\\) where \\(\\alpha\\) (n) is the inverse of Ackermann's function. Finding an upper envelope for appropriate system of linear functions solves a number of problems of computational geometry. Among the applications are mentioned problems of hidden line and surface removal, translating a polyhedron in the space with polyhedral obstacles, finding Voronoi diagrams of point clusters.","type":"string"},"datatype":"string"},"type":"statement","id":"Q919830$0CB91EF3-952A-4F7D-A2F7-CE5A90C657C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919830$2744A6F7-064C-442E-B97A-2518AF0D8912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919830$39D2CDAB-9EF0-4736-8E3A-EA30F3D02819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919830$17C2C5DD-EE9F-4ECB-9483-54F949F70766","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bec40db7d743be0b490e51f44730f64b61841dca","datavalue":{"value":"4162270","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919830$78F9B355-DB9C-41F8-B78B-36B7D76374CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bfd605e8d1eec2e403cfe1b9f8fb6385b43b4a0","datavalue":{"value":"visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q919830$A7EC0CB5-2BC8-420E-B407-B52F02318A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"662e2644eeb4eed253d92c3c2f6d29f89cd28ea1","datavalue":{"value":"hidden line removal","type":"string"},"datatype":"string"},"type":"statement","id":"Q919830$99718842-8347-452D-AF02-AC4FB39C1ABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7a39a1c143c36b9a508b6e0aad9580fb160eda5","datavalue":{"value":"combinatorial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q919830$0A543F9E-4B22-48E0-95A3-8E062299B630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q919830$B4B8F264-68EC-4CC2-B8B7-C35C05BBF7EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff324a78e200f704a90f188fa4d189ba6bab6331","datavalue":{"value":"surface removal","type":"string"},"datatype":"string"},"type":"statement","id":"Q919830$4F0337E2-BE35-4BCC-92AA-BF8DCBBB7B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2a942004e7c3ebf174ed889f18fd8e1f8b9b24b","datavalue":{"value":"Voronoi diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q919830$D8942ECB-00E8-4A1A-9138-A4DB753F1301","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$37160B15-8341-4E1C-AB7D-99EBE4F96EA3","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":"Q919830$B0569635-A945-41AD-91C0-D0745A0C8C28","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"697aae026a155134884ccf2d1f0ab3c5ec550b9e","datavalue":{"value":{"entity-type":"item","numeric-id":2638823,"id":"Q2638823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$30D75DEF-2030-4C4E-A15D-0FF3CA5817AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62a92cf1acfd64695513a6d70afd5dbd5e8e380","datavalue":{"value":{"entity-type":"item","numeric-id":3334982,"id":"Q3334982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$39256768-DF37-456F-B838-18775C90AA72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc68f2991d5ecf6a6ccd6dc3d6721e538e65f691","datavalue":{"value":{"entity-type":"item","numeric-id":4139673,"id":"Q4139673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$2A8FF243-A16D-480A-A931-5F85AA983046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$5134271F-D40F-44B5-B54D-05DC0457B965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe08fa8366507c93a27ade76495bc29f9a1ee07b","datavalue":{"value":{"entity-type":"item","numeric-id":919829,"id":"Q919829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$E345A86A-2B25-4727-85E6-5AED2EF720FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d87a027c696d4cca9cf462e499936419e44e67","datavalue":{"value":{"entity-type":"item","numeric-id":1163869,"id":"Q1163869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$960E8820-B08E-4F84-842A-100BC372E1F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83eade82042e507248d4b50c48d61d395faceaeb","datavalue":{"value":{"entity-type":"item","numeric-id":3358264,"id":"Q3358264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$7E3E2917-D0E3-401F-9F13-CB145C91B35C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"189f217450c64101167d90e0ab7fd4a0405a7a82","datavalue":{"value":{"entity-type":"item","numeric-id":1091816,"id":"Q1091816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$D4A49338-CD0E-4382-9DE6-6EF176EE4817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f7e43b624a4c37c3d64eb59c9ae4ec05b06aa27","datavalue":{"value":{"entity-type":"item","numeric-id":1262130,"id":"Q1262130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$B5C5217F-32B0-40F3-82F4-58FC5F0A5F3E","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":"Q919830$FD539810-7607-4412-AA27-2EF1BAAF3B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7033dd94767bf10e2700f8a7bd5817e2ced0a30","datavalue":{"value":{"entity-type":"item","numeric-id":4148820,"id":"Q4148820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$122F0E9A-61D0-4012-A818-C7A3FB2875B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae29f327c59780dea378339b809ffb2bf6e4bd12","datavalue":{"value":{"entity-type":"item","numeric-id":1076976,"id":"Q1076976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$7D7B800B-673E-4973-A087-5CB748BF1136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4b7b63704e574f5b12162cf3b779d2b3487b8df","datavalue":{"value":{"entity-type":"item","numeric-id":1084674,"id":"Q1084674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$9EABB7CC-6C8E-460E-B3AB-B1DD5BEA561B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7268624479a5bc435fdb2e9183ce011e018dd2bd","datavalue":{"value":{"entity-type":"item","numeric-id":810525,"id":"Q810525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$DB2408C8-31B4-49E4-A1E8-A8DE7EBF8D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"584205de1d391987ee461758c5d4a00a1c3eaf66","datavalue":{"value":{"entity-type":"item","numeric-id":1104080,"id":"Q1104080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$2F0A217F-B1F1-497A-9B0C-33A3846181D0","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":"Q919830$E5AAE1D9-753F-45DA-A953-467126D4F4CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04fa75793586e2df3bde0ba9553dc7701b47ffa8","datavalue":{"value":{"entity-type":"item","numeric-id":4775467,"id":"Q4775467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$941905B3-9A82-4079-BF1A-132FF4264A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53418c085fdd84a8e1310a8e29f810925f290273","datavalue":{"value":{"entity-type":"item","numeric-id":3792728,"id":"Q3792728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$D91BB58E-8987-4379-9AB5-556C1CF60801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$74CBF728-76B2-4277-8A31-3F4A696E012C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"179e0a9d46a8b7483726a7a65581cc4b382ad7bf","datavalue":{"value":{"entity-type":"item","numeric-id":3716330,"id":"Q3716330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919830$8E0788F3-D112-47B0-B7C6-80458E38A87A","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":"Q919830$E7225E38-1BD6-4A2B-A7F1-86931389110C","rank":"normal"}],"P1643":[{"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":"382ef7335a6ac5048ba8a6612ab840c937ecc5f3","datavalue":{"value":{"amount":"+0.8925637602806091","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":"Q919830$117F59AB-C5E8-46AC-BFFC-FA48B3F1F48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efcdf64824e3e249fa934a735c239c80cafba7eb","datavalue":{"value":{"entity-type":"item","numeric-id":810525,"id":"Q810525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"804cb816c21d76d7f6e92f25ca6c477a75ca7169","datavalue":{"value":{"amount":"+0.8376312255859375","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":"Q919830$94BCE7C8-B51F-4420-9B84-9784AEDC32C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d33eacc846d05877325dbf099e96c3bac6c821ff","datavalue":{"value":{"entity-type":"item","numeric-id":582095,"id":"Q582095"},"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":"Q919830$EFFAC42D-F011-4702-B3B0-CCF9B5082FCC","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":"249429fffe6e16f068c491d7f9c1cf236c76c0db","datavalue":{"value":{"amount":"+0.8272178173065186","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":"Q919830$36C66DD7-89F9-4596-A0F8-3F44CFF1EA06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d32ee2e8b80a0ffb689699aee740a7a449880840","datavalue":{"value":{"entity-type":"item","numeric-id":1907607,"id":"Q1907607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b822e8efa1586da9501b8d70e2c4352d614c6aaf","datavalue":{"value":{"amount":"+0.8269383311271667","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":"Q919830$0AAD1525-47D0-4F6D-94ED-CDDB5318B84D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:919830","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:919830"}}}}}