{"entities":{"Q1188284":{"pageid":1199033,"ns":120,"title":"Item:Q1188284","lastrevid":80168282,"modified":"2026-05-06T15:35:11Z","type":"item","id":"Q1188284","labels":{"en":{"language":"en","value":"The farthest point Delaunay triangulation minimizes angles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 40364"}},"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":"Q1188284$A03D0EB4-3B65-4C35-891A-9D12633EF928","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9cd2822a46a845a4d6015fe1395b5b0154be7fed","datavalue":{"value":{"text":"The farthest point Delaunay triangulation minimizes angles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1188284$E5054A1F-5D75-40BF-ABFD-3EE92D34A23F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50519807ec7ecccdd14aad4ad08dd599c540ead4","datavalue":{"value":"0762.52005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1188284$E8044F98-16A9-490C-85F4-53ADA23A4977","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d11c3a83230201f14c5e36a19341a1b27c43b210","datavalue":{"value":"10.1016/0925-7721(92)90013-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1188284$27E998F7-C4AB-40DC-AEB2-0029BEA9576F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c957339beeae6f46596c701e650eab7f54dbbfce","datavalue":{"value":{"entity-type":"item","numeric-id":283880,"id":"Q283880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$DF8163F4-393B-4016-8810-E5A42A137780","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":"Q1188284$F1934BF3-DAA6-4B64-9586-162C4A5D19BE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca50ef95d1c0114d462b29b2a7069fa309fbe2aa","datavalue":{"value":{"time":"+1992-08-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1188284$06149272-89B2-4B18-AF89-4CFD4A0F19D3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8c255f3255fa5b32b204677c62a745a0ece94590","datavalue":{"value":"It is known that for \\(n\\) points in the plane in general position (i.e., no four points are cocircular) the sequence of triangle angles, sorted from sharpest to last sharp, is lexicographically maximized over all such sequences constructed from triangulations of the point set. In this sense, the paper deals with duals to farthest point Voronoi diagrams of a planar point set \\(P\\). Considering the vertex sets of convex polygons (note that the farthest point Voronoi diagram of \\(P\\) has only regions corresponding to the vertices of \\(\\text{conv}(P)\\) it is shown that for general position the sequence of triangle angles, sorted from sharpest to least sharp, is lexicographically minimized. On that base, the sharpest angle determined by three vertices can be found in linear time.   The sharpest angle, determined by three of \\(n\\) arbitrary points, corresponds to a line segment bounding a face of the dual line arrangement and can be found in \\(O(n^ 2)\\) time. A faster approach would also speed up the detection of degeneracy (three collinear points or three concurrent lines) in a configuration. Detecting degeneracy faster than in quadratic time is a known open problem in computational geometry. The author hopes that alternate views on such problems (as his minimum angle approach) could lead to improvements in that direction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1188284$F5EE1FE3-9AF3-4926-ACDE-2DDAED7B64A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1188284$6C192662-C1BE-4164-A21E-CECC9B80A9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1188284$81A5A790-46CF-42F2-837B-4F9F7E2C9C41","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c7aaef82c1936f4bcfb68ee577fe4244f03eb69c","datavalue":{"value":"40364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1188284$7000E3BF-0346-43BC-90C9-C84CFC221D82","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1188284$CC7C97DF-88D6-44A6-9810-B0C323665852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1188284$FCC40603-63B5-41B8-95A3-87B2817831D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1188284$35859494-FB90-4FB0-A5BA-5F045A14831C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21a09e5a5dc90fbd5f16fcab89c178d0e65e14bd","datavalue":{"value":"farthest point Voronoi diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q1188284$A00828B9-7D52-4FDF-8D80-AE4ACA7FFFF9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a5031b3263da14f5abd118bd5a83bd1e3dacaeb4","datavalue":{"value":{"entity-type":"item","numeric-id":329396,"id":"Q329396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$A93C67B3-9187-4DFF-A227-D5EC91FDFB54","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":"Q1188284$DC2499BA-5110-49CB-BBF8-4D5B4626D2DC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9cd35177b9fbbefa725a3537ebfd136511c156e","datavalue":{"value":{"entity-type":"item","numeric-id":1135110,"id":"Q1135110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$C11136D8-44F7-46DA-8F52-BF3F19B9FE15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0bb2a78ba34e8728e91d77da2bf6df4e36bb56c","datavalue":{"value":{"entity-type":"item","numeric-id":3740283,"id":"Q3740283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$E0607158-D082-4DF6-AC95-74507DB2C3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"627648b2ea144ce15b27178c51fda0149103d9f5","datavalue":{"value":{"entity-type":"item","numeric-id":2942145,"id":"Q2942145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$8EB97B68-04B7-465A-97F6-78D253358E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b7ee5780baed1d7856c99389fada17672a0a4e3","datavalue":{"value":{"entity-type":"item","numeric-id":3898497,"id":"Q3898497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$EC3B4329-7082-48F0-BE32-9BFC90F17D9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89df0664294e2d2a4b0f0030dcb07d3bbc55bf65","datavalue":{"value":{"entity-type":"item","numeric-id":5056107,"id":"Q5056107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$8E3F9F13-B4C3-4411-B0E4-851F6C54A677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74331c2cae5cc2312cf94001756eb450e4256e7a","datavalue":{"value":{"entity-type":"item","numeric-id":3830566,"id":"Q3830566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1188284$916BC598-E37A-4B89-8CEB-B8983E84F743","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fcdc871773b30d3ede9ef74407ce3d4fc48d664b","datavalue":{"value":"https://doi.org/10.1016/0925-7721(92)90013-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q1188284$1A06BFA8-5130-45ED-B88C-BC58D6D7AF62","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"416f58c5713ad15de48f8236d7bc9a684853b056","datavalue":{"value":"W4240145741","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1188284$DAC35AE8-7E2D-4D78-BF9A-DEE7CABBA852","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27a366be230b63123a8dec9f89b2e2dfd038e0e7","datavalue":{"value":{"entity-type":"item","numeric-id":827337,"id":"Q827337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cb581867bb9eabde2ccb45e9f459a7100252b20","datavalue":{"value":{"amount":"+0.8622563","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":"Q1188284$D279770D-28CE-484D-B34A-B8694875A463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a01e434c4be7b28043b7cb88795f8b479e64789a","datavalue":{"value":{"entity-type":"item","numeric-id":4463093,"id":"Q4463093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2df40bba902d2077ed5def762782e45e3ac0cbfe","datavalue":{"value":{"amount":"+0.8620998","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":"Q1188284$2708E4CB-5D36-4AF9-9571-A9410E60A5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45f89fa1351f7e701e2d0cb7c971b87324f743f4","datavalue":{"value":{"entity-type":"item","numeric-id":751276,"id":"Q751276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd8c070d168394a683e60cb5d5cdc653373ae089","datavalue":{"value":{"amount":"+0.8539766","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":"Q1188284$6630622B-8528-4BDB-A4A2-65031C419F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d2311a74c8ed5c7ee2d66a6548c6d82b5d13ce3","datavalue":{"value":{"entity-type":"item","numeric-id":4028874,"id":"Q4028874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f8bda05aa85d153a8dc1f78f8a7d09b15439510","datavalue":{"value":{"amount":"+0.8486295","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":"Q1188284$7DCF12D0-5506-4617-ADC6-489501832866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5e356e1ccec86a9214f5a16d29620164e90f9c8","datavalue":{"value":{"entity-type":"item","numeric-id":722309,"id":"Q722309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"912f586f41b0312431030a52b2bdd27acf6bb6a8","datavalue":{"value":{"amount":"+0.8477114","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":"Q1188284$88A5FA64-2518-4537-9DD7-F888192D81A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b324651d817fe1ebcb8e3d60923e5d688058d3b","datavalue":{"value":{"entity-type":"item","numeric-id":4036603,"id":"Q4036603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bc83bdfc599a2f284d1f7e5e2a94d8c94e360ad","datavalue":{"value":{"amount":"+0.84731716","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":"Q1188284$66CF60FA-4A07-4538-A62A-FA32BEAD6947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8f4f37d6fe6e3082d8f113ac66b7e1009ea4af3","datavalue":{"value":{"entity-type":"item","numeric-id":3212323,"id":"Q3212323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bc83bdfc599a2f284d1f7e5e2a94d8c94e360ad","datavalue":{"value":{"amount":"+0.84731716","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":"Q1188284$8512FDBC-6E5E-41FA-8B80-A0D04C53F507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c185dba2be90b0c4ce39d036a747fd6e58d2389","datavalue":{"value":{"entity-type":"item","numeric-id":1334932,"id":"Q1334932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"145bb53c25d3818d9110e63a6096edf7868e5d2c","datavalue":{"value":{"amount":"+0.8466422","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":"Q1188284$00492FA2-E89E-48B6-B86A-ABB70D623956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfd5e88fb193821f77489d2b3d0e2680533a4d9d","datavalue":{"value":{"entity-type":"item","numeric-id":6072046,"id":"Q6072046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d149da8ffd6c9030e410747077d9a100be06c821","datavalue":{"value":{"amount":"+0.8464756","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":"Q1188284$EAF1C8D4-99DF-4181-A2C4-30598CDFF51F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf70dd3e165cb95bc36b8840a87fbaf5f33442aa","datavalue":{"value":{"entity-type":"item","numeric-id":1912647,"id":"Q1912647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b21f023c9beb95942d3cda8ef0985b346b282e42","datavalue":{"value":{"amount":"+0.84569144","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":"Q1188284$09BD2116-3F54-457C-91B4-E6B8B973791D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The farthest point Delaunay triangulation minimizes angles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_farthest_point_Delaunay_triangulation_minimizes_angles"}}}}}