{"entities":{"Q1115601":{"pageid":1126350,"ns":120,"title":"Item:Q1115601","lastrevid":66764847,"modified":"2026-04-12T12:42:09Z","type":"item","id":"Q1115601","labels":{"en":{"language":"en","value":"Constrained Delaunay triangulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4087015"}},"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":"Q1115601$634A9A13-BF23-4410-B476-629479145B3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"25ed5adf341957dc268840d8d0a9cdb326d12093","datavalue":{"value":{"text":"Constrained Delaunay triangulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115601$20C0CF8B-CF30-43D1-9346-8BC5D87B5FB2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e959c5e62308413677eb2aa943fce25d15c2d2f8","datavalue":{"value":"0664.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115601$D24E05C1-D5A2-4AA6-8A0A-2715BBE1D433","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"699ad42d8aecd06e77d850fe1f805d1bbe4d6a67","datavalue":{"value":"10.1007/BF01553881","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115601$D50BB110-5FAA-45F1-BB25-9DF30361018A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"36f72dc458dbb68417eed24578c25b37631aa961","datavalue":{"value":{"entity-type":"item","numeric-id":598236,"id":"Q598236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115601$B6669F8C-5F13-4A88-8275-DBAF8DCD5A48","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115601$9443492F-5C77-4E66-B800-8994A6F703E2","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":"Q1115601$FAB8669E-2CB9-4484-958D-DD102FA8F37C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c7b453892746f4d405137f8c1475b62afcd9e98","datavalue":{"value":"Given a set of n vertices in the plane together with a set of noncrossing, straight-line edges, the constrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimal O(n log n) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (non-Delaunay) triangulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115601$B5E86D14-29D5-41D7-8D40-BE61DB29B10F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115601$220C0A93-B1C6-43F2-A62E-4C14E8CA0FBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115601$B59F6434-8579-43FC-8CBC-DB04AAA35E6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5c044ff3938bf15ac6a779f52734b50e322f98c9","datavalue":{"value":"4087015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115601$9ACE1B95-27C9-4C73-A623-70884C84B131","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d64b39318b2fa93f4e091235dd0d345da5c53e5","datavalue":{"value":"constrained triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115601$77228A35-C9DB-4358-9561-A8A141F08FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d975c8e13006fbe9b4f6c347ea88f3b06e6e4c7","datavalue":{"value":"Voronoi diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115601$FA5C7422-9068-4802-AC13-CA9126EEAB36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115601$7D6008F2-5662-480D-9714-F8E908D96BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115601$5270C746-929C-4ECE-8D4B-7800E066D38E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7524eff3be377b3373bf1ae15aa61fe821e44b35","datavalue":{"value":"divide-and-conquer","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115601$DB0EEF9D-2D68-400C-AE06-9E8A2DED584D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a2c9038953217ca15dfb95469bc40bcc673946f","datavalue":{"value":"finite-element method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115601$F4832AFD-9AE7-4CF6-9474-18FDC0C3FA10","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":"Q1115601$A8F622D3-888A-4131-99DE-9D34055CB50F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"11ec8827985a70c134d275ef3d27a03bce34dc1f","datavalue":{"value":{"entity-type":"item","numeric-id":3026390,"id":"Q3026390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115601$C024809F-8566-4C30-885F-D4E4771E4F6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99114b1bd38a031039ee6a9bed0217048b0b5658","datavalue":{"value":{"entity-type":"item","numeric-id":1101224,"id":"Q1101224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115601$83A4D59F-5217-472E-BC64-94B995EAF34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cceec15e0bf6f1544f3e1864012ec31a05ee6eb","datavalue":{"value":{"entity-type":"item","numeric-id":1078807,"id":"Q1078807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115601$1F0D2BEB-8BCD-44B5-916A-6EFEE31D311C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"794e24faea6d10ca38a88bb803e4681f9768e955","datavalue":{"value":{"entity-type":"item","numeric-id":3883495,"id":"Q3883495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115601$5D67B1E4-0EA6-4669-BBD9-73D7236DEB66","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":"Q1115601$65DC62DE-6DF0-4380-A0D2-4F51215A6F26","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cda1a9ff828cb7f32dc63a890f5a29fc5b30e87f","datavalue":{"value":{"entity-type":"item","numeric-id":5174490,"id":"Q5174490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e92eaa58874d943a55a2eed16c35b045bd44b68b","datavalue":{"value":{"amount":"+0.8714911937713623","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":"Q1115601$F8B3FF85-7DE7-4E78-A18B-0334633F0F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"888f0faa0ff0447f4c54193c537d38f8f4e8aaf7","datavalue":{"value":{"entity-type":"item","numeric-id":2354921,"id":"Q2354921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dec5cfde5ad8159654bc105910223bd49046cf8f","datavalue":{"value":{"amount":"+0.8667947053909302","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":"Q1115601$2ECCC134-5FCC-4DC9-9A18-51CCC69D8BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d056597d065dac202c1562c04abf0ae3b95b857d","datavalue":{"value":{"entity-type":"item","numeric-id":2482216,"id":"Q2482216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d38f39a94fb5ada6d21e4d4e28f22523c807b09c","datavalue":{"value":{"amount":"+0.8656967282295227","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":"Q1115601$56E21F41-C6C4-4DC3-9449-A18764365190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b06d1bc1421c8e3aad0cd65daf5f8eeee5aa82a1","datavalue":{"value":{"entity-type":"item","numeric-id":3619957,"id":"Q3619957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6852e52158a2209d46be3a2eedf5b626fb1466a9","datavalue":{"value":{"amount":"+0.8645007014274597","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":"Q1115601$D0BF7BEE-FF3D-4D5B-AD84-499F63336B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b343ea6eb026b5146c0fae58ba5ea5ff536838ba","datavalue":{"value":{"entity-type":"item","numeric-id":688628,"id":"Q688628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ca00071883a0740ec56d28b0f04c3a2805104f1","datavalue":{"value":{"amount":"+0.8515480756759644","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":"Q1115601$77A8C8DD-9F3E-4CE0-AAED-9E5703A79E40","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Constrained Delaunay triangulations","badges":[]}}}}}