{"entities":{"Q6639378":{"pageid":14250530,"ns":120,"title":"Item:Q6639378","lastrevid":55973275,"modified":"2026-02-21T16:00:39Z","type":"item","id":"Q6639378","labels":{"en":{"language":"en","value":"Largest unit rectangles inscribed in a convex polygon"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7945400"}},"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":"Q6639378$7FF2B717-A7FA-4DB9-8CB8-AA4699372599","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"21d7f9b1ef4933d23e101cc6c8bae2216fbd1748","datavalue":{"value":{"text":"Largest unit rectangles inscribed in a convex polygon","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6639378$D59EB8BA-32C4-4593-8615-A8F4D3EEBC77","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd5dc012f3f8d071ff62f48c77f2d23b6ce28b70","datavalue":{"value":{"entity-type":"item","numeric-id":6604614,"id":"Q6604614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$82AA1EAE-5A28-4445-8F4E-C4E80F2DCB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aad2244a0fac49ecd6eb575ec97eea59fe9c09ce","datavalue":{"value":{"entity-type":"item","numeric-id":283874,"id":"Q283874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$82AB03CB-30DB-437F-906A-5FBDCEF49800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fba8ae1f15f532d7104ee9a8930ec5ceaa2ea810","datavalue":{"value":{"entity-type":"item","numeric-id":216327,"id":"Q216327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$88E49A37-9E99-43A8-A830-EF3AD134455F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"468c95a2fd517e40877ed89abb109d02f87b5ed7","datavalue":{"value":{"entity-type":"item","numeric-id":528486,"id":"Q528486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$DF88FB07-0220-41DD-8B2A-0AFEC82375AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a93a947551675282cc493935b29c7f4b55cf2b2a","datavalue":{"value":{"entity-type":"item","numeric-id":364849,"id":"Q364849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$F72375BF-995C-4B8B-9A25-3C238736AF5D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$79423F17-8356-4479-99BA-CF9182B71B71","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"766bbc3e4a23e7a800cf46cd9ae3e5e68d6d6874","datavalue":{"value":{"time":"+2024-11-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6639378$1BF0AFEC-F871-451D-954D-3C769BA56F66","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"78ac2fa97eb2e079f35389ddd56edd949a4b1cdf","datavalue":{"value":"The authors investigate the problem of finding the largest unit rectangle that can be inscribed within a convex polygon, specifically a convex \\( n \\)-gon. They present two distinct algorithms for this purpose:\\N\\begin{itemize}\\N\\item[1.] An \\( O(n \\log n + U) \\)-time algorithm, where \\( U \\) represents the total number of intersections between unit circles centered at the vertices and the edges of the polygon. This algorithm achieves a time complexity of \\( O(n^2) \\) in the worst case when \\( U = \\mathcal{O}(n^2) \\), but performs near-linearly in most practical scenarios.\\N\\item[2.] An output-sensitive algorithm that runs in \\( O(n \\log n + n/h) \\) time, where \\( h \\) is the height of the largest rectangle, which allows for more efficient execution when the height is known.\\N\\end{itemize}\\NThe paper also emphasizes the practical relevance of this problem in real-world scenarios, such as industrial applications involving spray guns with strip nozzles, scan path planning for defect inspection, and others. Finally, the authors raise two open questions about the combinatorial structures of inscribed unit rectangles, which stimulate further investigation into the problem.\\N\\NThe topics of the paper are interesting. The manuscript presents a well-written, theoretically robust, and practically relevant solution to a geometric optimization problem that has significant real-world applications. The authors' algorithms provide an efficient approach to solving the problem, and the paper is well-structured, making it accessible for readers in computational geometry and related fields.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6639378$71771F05-D432-4333-AB52-BC86D1DEA341","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aa08d1013369aebbeb84e03f2c01fa22cac0d74c","datavalue":{"value":{"entity-type":"item","numeric-id":427615,"id":"Q427615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$A2165C20-DCA6-4C45-BCB6-B258111CF8FF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d37df3eeaabc93671e85ccca30b22399444c5039","datavalue":{"value":"52C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6639378$33A4D149-CE73-4A9A-9991-9C5763F40ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6639378$2A414458-8D70-4FD6-A084-7A32768B39FB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c44f039ca2cf3c54b0ebed5affbc98399495837c","datavalue":{"value":"7945400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6639378$D57CED81-961A-4886-9723-D7CBD186B26B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5a50a5a67308669ffa8f373af4072feffe8d81b","datavalue":{"value":"unit rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q6639378$EA5A46C5-F9CD-4548-A9B4-2C1E0B12D329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fa312182bb7eaae3fd62e5da43ed90b053a6af4","datavalue":{"value":"convex polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q6639378$C70F4C28-1F0C-424C-844E-E495EB01964C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c27024bc3112e6fbf1cca0a9a4aacb8e7e4a77e0","datavalue":{"value":"optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q6639378$934A300D-8ADA-49C4-A156-06891BF5DFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c398d66ceeb263ce9170a5ce92491cae29e1a343","datavalue":{"value":"time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6639378$57575099-CF49-4A83-B0FA-31395FF6588B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58d1c451e396db63624dc61fd52bb30b0a7737d0","datavalue":{"value":"output-sensitive algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6639378$3D87FF69-65B0-4FA5-9386-BB4B5D270BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e688b324cf1d84383a2b39e4ce0810fc2204188","datavalue":{"value":"inscribed unit rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q6639378$FFC35805-A658-418C-B483-4603EBAF011C","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":"Q6639378$B3FA065D-56BC-4AF3-9135-416858864580","rank":"normal"}],"P223":[{"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":"Q6639378$C4A633B7-5009-463D-B33E-9E0A3DFEA811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb02736cbf1cd475b47f64284d0eceecb2f6fc56","datavalue":{"value":{"entity-type":"item","numeric-id":2489540,"id":"Q2489540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$342466A9-4399-4406-98CF-E83BF9B1A430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3abf9b7d72a7f68eb6ba175ed4964db474dddd0","datavalue":{"value":{"entity-type":"item","numeric-id":902427,"id":"Q902427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$00ABE495-1BAC-41D4-AF71-6AE23728041B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42c6d852be18ae77ef309660b4ddf583e7dead77","datavalue":{"value":{"entity-type":"item","numeric-id":1076347,"id":"Q1076347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$61992A5C-6EFE-4D21-96ED-05263A3185D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ef40a13870088db16541407f714d88be5cbf47d","datavalue":{"value":{"entity-type":"item","numeric-id":705130,"id":"Q705130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$4ED1D115-0064-4AC1-A170-6608EB58D74D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"155583873c96ed81f8b283093c1db183fba96fef","datavalue":{"value":{"entity-type":"item","numeric-id":827336,"id":"Q827336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$CBF1F253-8B8F-456A-9CB5-6927506C72DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe9ac18451d6522d3dc0b699ed548d3adfd714f2","datavalue":{"value":{"entity-type":"item","numeric-id":2349786,"id":"Q2349786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$94614555-FE6D-444E-A290-1DEFCCEA2A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"589e7ca968bebb22b45973249262008b28776827","datavalue":{"value":{"entity-type":"item","numeric-id":6604615,"id":"Q6604615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$9F557CF5-073F-4541-BDFF-329645526422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4241f8308d167565bbead4d0eec3525ac106e02b","datavalue":{"value":{"entity-type":"item","numeric-id":5452284,"id":"Q5452284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$B2F6129F-3405-4C88-8F0A-D63075127D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5243f4835e96b08a3f61385b2a8f8b0a9ceb1588","datavalue":{"value":{"entity-type":"item","numeric-id":1202051,"id":"Q1202051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$8E288D32-D754-4B8B-8D00-EAD0B8DC0FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f3fd7038eccaa9b4c3344bec2f45041147bf34","datavalue":{"value":{"entity-type":"item","numeric-id":450533,"id":"Q450533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$F6B3F8AC-94E0-4F13-ADDA-3ACFA1795FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9162a50c77ed562b679e16ecf16508106d20c9bd","datavalue":{"value":{"entity-type":"item","numeric-id":2230417,"id":"Q2230417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$49887C26-1260-4943-A85B-E73888ECFDF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63a4efb51191d6e7ab5f3b1db38cd4032f090394","datavalue":{"value":{"entity-type":"item","numeric-id":783698,"id":"Q783698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6639378$93550109-ADB1-4491-BA03-D9A4D585AF1C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"614b6dd4e2913b89b1fc5c66713989522e97d905","datavalue":{"value":"10.1016/J.COMGEO.2024.102135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6639378$6DA64166-227D-4ACA-A13B-495B0325A395","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9357a12c79e6bfdd06610876bd0e7e315493357f","datavalue":{"value":{"entity-type":"item","numeric-id":902427,"id":"Q902427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2677dac1954d4ff42aeefc99be9d68ef7ca38384","datavalue":{"value":{"amount":"+0.805928111076355","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":"Q6639378$A565B50F-A1C9-423F-8CFF-A88BC1E60A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"508be3707a591437d9ec94f5c1d63c1b98101910","datavalue":{"value":{"entity-type":"item","numeric-id":450533,"id":"Q450533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b7abfd388dbe44be3dd4582b4ae7278dc0f3433","datavalue":{"value":{"amount":"+0.7968900203704834","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":"Q6639378$3A8A4AEA-8C78-46D2-985B-46BD70F7F334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"848f913fe54239c11adc9c53b3ff7f68da655767","datavalue":{"value":{"entity-type":"item","numeric-id":827336,"id":"Q827336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afeaa0ed8e1ae97a9260efd3684feaa1da138fcf","datavalue":{"value":{"amount":"+0.7817811369895935","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":"Q6639378$7A4FEA95-EBC4-43CB-A61B-13581926BB21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1488aee32df94c6bdb608234c6135cebe9a4c1d6","datavalue":{"value":{"entity-type":"item","numeric-id":440979,"id":"Q440979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a88f06ce04f75863b4814d298c59518eab232e00","datavalue":{"value":{"amount":"+0.7527540922164917","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":"Q6639378$053D4DC8-9F89-42DA-B6B1-B2D829C9C1E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5451558b858b1c36868d9cbb01572bdb937c58f3","datavalue":{"value":{"entity-type":"item","numeric-id":676593,"id":"Q676593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"477916ca8f250b5b87c21dce34c921a2c5b324b3","datavalue":{"value":{"amount":"+0.747463047504425","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":"Q6639378$7F770C35-F1E2-46A1-A9E0-517BBC7D5BC1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6639378","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6639378"}}}}}