{"entities":{"Q913505":{"pageid":915353,"ns":120,"title":"Item:Q913505","lastrevid":65333409,"modified":"2026-04-12T01:51:55Z","type":"item","id":"Q913505","labels":{"en":{"language":"en","value":"Applications of generalized matrix searching to geometric algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4147502"}},"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":"Q913505$261612BB-FB8A-47A3-82AC-E02E50D2A23C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"45843b773224daaeca9de9e157dafa665f635b98","datavalue":{"value":{"text":"Applications of generalized matrix searching to geometric algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q913505$9EF3AFCC-7396-4285-A725-67F779BB81E5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f1aff62f7921db9debaaf5bace73c6082506248f","datavalue":{"value":"0699.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913505$C0B23CDD-9936-4A8E-8C80-92773D57582D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9cb421c89ca5acdc889491f847ccc16fdd47df2","datavalue":{"value":"10.1016/0166-218X(90)90124-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913505$5017BBDC-58FA-4E48-BD7E-66D827378C9C","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":"Q913505$7C365284-742D-484D-8895-D22B27BC7768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a25d6c9ed2c7d3c838dcd849030b5593bce4a77","datavalue":{"value":{"entity-type":"item","numeric-id":1058850,"id":"Q1058850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$E9FA8C8E-A97B-467E-9A8B-88446C6FD957","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$74F52A3F-F58B-4674-9EB0-D5ED5655EE72","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":"Q913505$3EA99B47-C5EE-4FCB-8BC5-6FA825078235","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b9e86661989b0fd20d66a85253a28e72034fdedd","datavalue":{"value":"This paper introduces a generalization of totally monotone matrices, namely totally monotone partial matrices, shows how a number of problems in computational geometry can be reduced to the problem of finding the row maxima and minima in totally monotone partial matrices, and gives an \\(O((m+n)\\log \\log n)\\) algorithm for finding row maxima and minima in an \\(n\\times m\\) totally monotone partial matrix. In particular, if P and Q are nonintersecting n and m vertex convex polygons, respectively, our methods give an \\(O((m+n)\\log \\log n)\\) algorithm for finding for each vertex x of P, the farthest vertex of Q which is not visible to x, and the nearest vertex of Q which is not visible to x.","type":"string"},"datatype":"string"},"type":"statement","id":"Q913505$9200F054-9476-43FD-B1B3-E4DAC63A0926","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913505$0134D4BF-FCCD-4528-B101-542CDDBB6883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913505$00778123-E2CA-4139-82FA-92171E2B84B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913505$EACEFF9C-15FD-49CA-A5FE-D4358C36C546","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f30c2de28aaf6f6dea04a8a37d64431bef313836","datavalue":{"value":"4147502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913505$3E98B94D-C1BD-49BC-B0BE-503CF3FD2D85","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a59b1493a3dfce77efe9c02f17396ec193aeaaf0","datavalue":{"value":"optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q913505$E8027786-6D77-4A8C-99B8-E9ED5F6EA44F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff89dc6015c56ba43c910a48237897bdb99d7730","datavalue":{"value":"totally monotone partial matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q913505$8ECE830A-88A9-4664-8DF4-33A37A281A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q913505$CDCAD51B-2254-4501-A625-B3E74970E1C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35daefd8f279241a892c19fb5c643034a6acc10a","datavalue":{"value":"row maxima and minima","type":"string"},"datatype":"string"},"type":"statement","id":"Q913505$70487530-4158-4621-A93A-59D911FEFEAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fa312182bb7eaae3fd62e5da43ed90b053a6af4","datavalue":{"value":"convex polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q913505$EC88A85A-4FB5-4151-AF4F-339A96DFB94D","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":"Q913505$76FDEA31-A6B4-4E2D-AAFB-F883DF8BE054","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1ec42051c06d10a6971842b064f7570467f0308","datavalue":{"value":{"entity-type":"item","numeric-id":911267,"id":"Q911267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$FE45937B-7A15-491D-8459-3E47876B9F16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e78add1d8b013583dbc6de9c2424cecf91acefae","datavalue":{"value":{"entity-type":"item","numeric-id":1101223,"id":"Q1101223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$539C413D-C150-42DB-BFB5-A3D09F9C2568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef7e9681d49f2df035d9c81024a2a9090eccea91","datavalue":{"value":{"entity-type":"item","numeric-id":3747743,"id":"Q3747743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$68B95BC2-30EE-4DA7-A61B-1698EDAA6E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"134d6b539f310025b7a53e1ab7889fe3d3557d8f","datavalue":{"value":{"entity-type":"item","numeric-id":3697818,"id":"Q3697818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$7396B649-7E9A-433B-83E1-F803540E6F6D","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":"Q913505$BBE26AF5-008F-4BCB-9AAC-8DA66BEFABA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e711769a05281bc5ed6556f83316065c5945b41","datavalue":{"value":{"entity-type":"item","numeric-id":3031930,"id":"Q3031930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$BA6112D4-A5B1-4ECE-B7DE-E34BD16D9518","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":"Q913505$D4126C09-1971-4ABE-B19A-EFD88C637D18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab9002c6ee03c89bc48bc9e3b89404864edba99f","datavalue":{"value":{"entity-type":"item","numeric-id":1250433,"id":"Q1250433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$A956FF80-6752-4D03-B5BF-514C7621CD86","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":"Q913505$D9D685CA-5C31-478F-B582-8969117944B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b0ea9107292543579c21ea0c0cb14a4149357c5","datavalue":{"value":{"entity-type":"item","numeric-id":3716336,"id":"Q3716336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$A987B53E-738D-4C23-B6A2-114A3843814A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d926df343880b7eb5dd1e71fb5436462549f57ee","datavalue":{"value":{"entity-type":"item","numeric-id":3777964,"id":"Q3777964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$E1B9B569-7EDA-490D-88F5-5D58CDBE4DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35d1904e2202079745d43a54b9e1cd4db59a1fc5","datavalue":{"value":{"entity-type":"item","numeric-id":3796787,"id":"Q3796787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913505$139EA668-BD30-4B2F-AB08-FDEFE892DCF9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8cb15639db0933d747dfa4bff6792772a48bd479","datavalue":{"value":"https://doi.org/10.1016/0166-218x(90)90124-u","type":"string"},"datatype":"url"},"type":"statement","id":"Q913505$6472BDC6-8A1E-4F43-BC21-4D1261519FE7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bbf4a171f0d4ceeb77b9136e05e9d9b27da9ae8c","datavalue":{"value":"W1994172977","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913505$22B267C4-09F3-4F2A-AAD4-11B705FA2475","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ed9cd90c9bf78f4afcda0b4d5d048f263b59df9","datavalue":{"value":{"entity-type":"item","numeric-id":1101223,"id":"Q1101223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"171e0efbaa5fab97f2f980cb86b41659e8427681","datavalue":{"value":{"amount":"+0.9106128811836244","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":"Q913505$B2219A7B-920D-4A63-A837-69C627755BAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0caa93f7312ebace81c9bd78e8b7d6c2548b7a7","datavalue":{"value":{"entity-type":"item","numeric-id":3031930,"id":"Q3031930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3a76810ef1bf420233ecc87b7e7dcfef842350a","datavalue":{"value":{"amount":"+0.8590997457504272","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":"Q913505$5EF68B94-CA76-4F53-85FC-823ABDD2D157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29202639ee1ce7b5be791ffc04b15090cfd9d8ca","datavalue":{"value":{"entity-type":"item","numeric-id":4376191,"id":"Q4376191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddc9a415c55086364b4dcbce996953e773c49263","datavalue":{"value":{"amount":"+0.8306419253349304","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":"Q913505$42C78FE3-D801-4E51-9952-9E79AD8B23F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bef5656584fe071af6fb2af9d73d3647ab2e1195","datavalue":{"value":{"entity-type":"item","numeric-id":3990615,"id":"Q3990615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"358ec593cb80e4887d7ae177d5c05784d36ba9d8","datavalue":{"value":{"amount":"+0.8040765523910522","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":"Q913505$E619717C-DDC1-4D9F-904D-632E17D4FF3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85661a68e7da645e8e18b9b3eb6606fa868920fd","datavalue":{"value":{"entity-type":"item","numeric-id":3979609,"id":"Q3979609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac7353867f272a31bfd85f74c8d1467a6e6aa1d5","datavalue":{"value":{"amount":"+0.8027084469795227","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":"Q913505$EC564283-445A-428A-A327-C0E7C1FC729F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Applications of generalized matrix searching to geometric algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Applications_of_generalized_matrix_searching_to_geometric_algorithms"}}}}}