{"entities":{"Q1824391":{"pageid":1835133,"ns":120,"title":"Item:Q1824391","lastrevid":73454475,"modified":"2026-04-14T16:03:22Z","type":"item","id":"Q1824391","labels":{"en":{"language":"en","value":"Does a point lie inside a polygon ?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4117857"}},"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":"Q1824391$B156A384-57F9-440B-B1E6-816A075FA740","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa46dcb97c88a680209eb79957e2154c6abab9f9","datavalue":{"value":{"text":"Does a point lie inside a polygon ?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1824391$C45A13CF-C1A6-4031-AB9E-0CA088B85B30","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"36b5218af49d345eb278a47f8e27054d8fb0622f","datavalue":{"value":"0682.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824391$051ACDA0-AABF-437F-85C1-15BCBA6B8238","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fc5537db96898ae2f7640b8bc3257801770bc10f","datavalue":{"value":"10.1016/0021-9991(89)90185-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824391$7DEE4D17-619A-47EF-B794-3282B1E72D78","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6cceddc06ad0ad76fac52687780769138ba9c5f9","datavalue":{"value":{"entity-type":"item","numeric-id":164235,"id":"Q164235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824391$E5A77734-F296-4664-908C-5B014204BD86","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":"Q1824391$37029215-DF2F-4445-A792-357F442CCCDB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e3e619d05803de431ce1dcdb6f61c44bd343f1f4","datavalue":{"value":"The algorithmic question raised in the title is a special case of the so- called planar point location problem that belongs to the fundamental and well-studied problems in Computational Geometry. Of the various results known, three simple approaches are reviewed: two linear algorithms that work for arbitrary planar polygons, and an algorithm of logarithmic worst-case run time for star-shaped polygons. The author proceeds by proposing a new algorithm that works for convex polygons only but needs linear run time in the worst case. Optimal solutions to the point location problem can be found in \\textit{H. Edelsbrunner}, \\textit{L. J. Guibas}, and \\textit{J. Stolfi} [SIAM J. Comput. 15, 317-340 (1986; Zbl 0602.68102)], \\textit{D. G. Kirkpatrick} [SIAM J. Comput. 12, 28-35 (1983; Zbl 0501.68034)] \\textit{N. Sarnak} and \\textit{R. E. Tarjan} [Commun. ACM 29, No.7, 669-679 (1986)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1824391$71E075F6-9EB8-4FEA-AA3A-ADA1CEAEA198","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824391$B56A360B-93E3-4EE9-8474-CBC8A4033B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824391$5CD43565-2D95-4E1F-A3A7-3F66D6277991","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e9fdcd1cb0f9b3de30583916bba2147e8963c67d","datavalue":{"value":"4117857","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1824391$FA5886ED-87BB-4403-B850-CBA9ABC2334A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53521e0d39d9437a6cd98b68287f0e922c40c02f","datavalue":{"value":"planar point location","type":"string"},"datatype":"string"},"type":"statement","id":"Q1824391$0E293E54-635C-4E0D-939A-87F2E1BEA1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d03344a3a5c0340170e3a2293ae030e811ae28d","datavalue":{"value":"Computational Geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1824391$BF3C7926-358B-47BC-956A-A58B6E646835","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5377b909794dca4106f410f32bbeda9dbe834e93","datavalue":{"value":{"entity-type":"item","numeric-id":355653,"id":"Q355653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824391$5B85885A-A49A-4CFE-B515-45F9806E607D","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":"Q1824391$B6446660-F230-495B-83C3-A690BEDACE3D","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":"Q1824391$854684EA-EB02-4CB2-862B-FB132A89D46F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f09abd8d09729dc67252881c661ea2453195bec5","datavalue":{"value":{"entity-type":"item","numeric-id":3219753,"id":"Q3219753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824391$3F43CCA8-FEAF-4F2C-B624-4BCDD436CC50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29b726da21df44f9fdc17f8c0d089fbede74a663","datavalue":{"value":{"entity-type":"item","numeric-id":3940877,"id":"Q3940877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1824391$BE470B3E-2A00-440D-82C8-D4F5424E95D4","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":"Q1824391$14A904B5-0DFF-4E03-BAD7-11B612CCBC18","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6d3ab6dff46ab0fb17a31361ee7e766790d029b","datavalue":{"value":{"entity-type":"item","numeric-id":268543,"id":"Q268543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"827ae0d01acdd02f872dc0cc7fcd130ed6155ec0","datavalue":{"value":{"amount":"+0.7577802","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1824391$A67E1826-6BBA-4A64-819C-2392723BA856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bef950c295a2d1a972a4d784f70af0a0aacca7a7","datavalue":{"value":{"entity-type":"item","numeric-id":5364983,"id":"Q5364983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5311e7b925bd74c90e4b35cf324086f9a0abb62f","datavalue":{"value":{"amount":"+0.75049955","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1824391$9EA64468-4239-46C2-B558-7E2B436799B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6ca8316c4c75bc2f1907af2ae0f3e0bd0d2bced","datavalue":{"value":{"entity-type":"item","numeric-id":3103482,"id":"Q3103482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"868cdb0db09c79d09693eb2f74fad4b2ca2140fc","datavalue":{"value":{"amount":"+0.74081266","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1824391$FAEC385D-A35C-4077-AF25-56825DB7A632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21976065dba651e406a47e2870990fcf4a7d39f5","datavalue":{"value":{"entity-type":"item","numeric-id":5952585,"id":"Q5952585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81945965149b50e8aef03b90c560205ef94fd604","datavalue":{"value":{"amount":"+0.7312715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1824391$D88C3971-D0F3-4A23-AF84-81814ED3C20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac3ee3fe7f425fba0af98e2f41e3d62792ce9aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3817601,"id":"Q3817601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5d1e12b6eb86b9517607b111bd3d1540eee4023","datavalue":{"value":{"amount":"+0.72206616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1824391$40611117-70B7-4921-A908-8C540D18A1DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6862f0669753ed7dd3f4d34d10cd15496e9f0e96","datavalue":{"value":{"entity-type":"item","numeric-id":2804847,"id":"Q2804847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aec9655e55db6ec23bce3575540f4b940e37dc7c","datavalue":{"value":{"amount":"+0.7206282","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1824391$DE33E305-2A78-4ADF-A0BC-BD83BBA27810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d78af2f0f850a4dd041ef90313cadc27d67414c2","datavalue":{"value":{"entity-type":"item","numeric-id":2477192,"id":"Q2477192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a58779b9bbc5239eda42c160cc02dfb552a2572","datavalue":{"value":{"amount":"+0.71810204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1824391$4ACD7D52-40D9-4752-B365-347164712F39","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Does a point lie inside a polygon ?","badges":[]}}}}}