{"entities":{"Q809630":{"pageid":811478,"ns":120,"title":"Item:Q809630","lastrevid":64539306,"modified":"2026-04-11T20:34:05Z","type":"item","id":"Q809630","labels":{"en":{"language":"en","value":"A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4213499"}},"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":"Q809630$818EEFED-90DD-4E43-AE61-BA4549FA1A85","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2de3c69f6e0c77eeeca7c69d797870590f14c8f3","datavalue":{"value":{"text":"A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809630$B5B503B5-2A92-4A6C-8016-3266E148A5E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0200b46f8f38d9b522ff6c8189f47ffdf6e7b70e","datavalue":{"value":"0733.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809630$23C1D13C-DAB3-4D17-819A-0C31937F4CEC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aeaa68d102fe44540684bfb80aa4ebdf88d13f84","datavalue":{"value":"10.1016/0925-7721(91)90012-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809630$6F5234C0-5F6F-4296-95DA-D8B91CE84539","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b616ea83f16323d1b4f0e42f503e6129370f5d6d","datavalue":{"value":{"entity-type":"item","numeric-id":686136,"id":"Q686136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$51CB050A-C80B-4DF1-B905-13669C3C9C2E","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":"Q809630$10200179-82D1-4209-A678-0514E5A8151F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q809630$6DB062AE-F0BE-41BF-A31B-3CC0D05313E3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cdea91f3e37584a79e8b6680590363e661560f98","datavalue":{"value":"The construction of the ``trapezoidal decomposition'' alias ``horizontal visibility map'' for a planar polygon is a common preprocessing step after which a triangulation may be constructed in linear time. This data structure for a set of noncrossing line segments is also useful for a number of other applications, e.g. motion planning and boolean masking operations for VLSI layout.    The paper presents a conceptually simple randomized algorithm which constructs the trapezoidal decomposition for a set S of n noncrossing (i.e. intersecting only at their endpoints) line segments in the plane in the expected time O(n log n\\(+k \\log n)\\) where k is the number of the connected components of S.    \\textit{B. Chazelle} [Discrete Comput. Geom. 6, 485-524 (1991)] proposed an ultimate linear time algorithm for polygon triangulation. However a practical and simple to implement triangulation algorithm may be based on the trapezoidation from the reviewed paper.    Additionally, the algorithm creates a data structure of expected linear size for point location queries in the resulting trapezoidation in logarithmic expected time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q809630$15033BA4-132E-430A-9E41-BF1A086DCD99","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"257d0165052e5019ac8fd49a93c7aebbdcc243c0","datavalue":{"value":{"entity-type":"item","numeric-id":751866,"id":"Q751866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$5D1A3AB3-08EC-4B29-84E0-106170312D9A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809630$DD42337E-788E-4681-8D86-BC8E44DB64EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809630$3E54395C-C869-4E54-BCA8-E4DC66E320AE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64de1bb1cc5cbfa71b6c4fe5bebfa175715e4911","datavalue":{"value":"4213499","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809630$2D4D10FB-5480-4BC9-ABB3-CEDE9C5D6736","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b198546508854bcc521c452e3e0681a16812ba9","datavalue":{"value":"polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q809630$5944C59E-42A6-4758-842C-8727E7C1161B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd3b97137fc5cddeb53bb49b8b441b42d47d65a","datavalue":{"value":"triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q809630$7BC6B75C-B064-45B5-9B55-C7BD69DAABF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a8c2738b6e6b9bdd4788fe09d0944b9eb13d293","datavalue":{"value":"visibility map","type":"string"},"datatype":"string"},"type":"statement","id":"Q809630$FAC35696-2684-4F13-ACA0-B5DD558D32A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c04cd4364c11601672fe554a7777dc06c47d158","datavalue":{"value":"trapezoidal decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q809630$2800A379-D48C-44E0-A1B6-8654DCA904F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q809630$7674975D-8873-47EE-BA0B-AE241EF577BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e930e55642692c0a336297e3fc16edcba6735e52","datavalue":{"value":"point location","type":"string"},"datatype":"string"},"type":"statement","id":"Q809630$75B5BFCD-6741-4BBF-AFCD-4B0E189E93D9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9100d5a708b56bd8348df087664ae7934a8d1da9","datavalue":{"value":"Q56389444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809630$51C29CBB-8C3E-4897-A3CC-CD0C00F3CB77","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":"Q809630$08AEB2D6-74FC-4DA8-9800-A1DEA9C9172B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d20bc2814f92f470eef1f9a6ccf2d2c98fe51c5","datavalue":{"value":"https://doi.org/10.1016/0925-7721(91)90012-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q809630$5BD03C30-89E5-48A8-A133-CC92E5516EE2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1ba280e0e01e23c40b1eadc170e84baf9a10dd8d","datavalue":{"value":"W3011379640","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809630$0BA47F39-E7BC-47C6-BC70-72FDEC630C71","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14bb5de49d1025f33147045f216b73559caa6b2","datavalue":{"value":{"entity-type":"item","numeric-id":3721846,"id":"Q3721846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$D29B0381-CE95-4566-A75C-3A45151DB92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29e36fdb885a1000809d41b1d6001037b2e2e0b0","datavalue":{"value":{"entity-type":"item","numeric-id":4030354,"id":"Q4030354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$3C596C6D-30DD-43ED-846C-409EC3204BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edb11b0dca7253830be5f8139bd13817d5fa1992","datavalue":{"value":{"entity-type":"item","numeric-id":1823686,"id":"Q1823686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$BC000459-8A4B-4ED7-AA88-AEF933834739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f0a1a2b9bf668daa897de5ce6a3be86456a7969","datavalue":{"value":{"entity-type":"item","numeric-id":3721847,"id":"Q3721847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$15FEAFC1-49B3-42A5-976D-D179B010FDCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae0713540eb691df7bd8820bc004fcb597f484c","datavalue":{"value":{"entity-type":"item","numeric-id":1249042,"id":"Q1249042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$CD6E63F4-999A-424B-AC1B-E9B224D418FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b12fa80e0883c7916ad7ebd37bad50bd07b508","datavalue":{"value":{"entity-type":"item","numeric-id":3670558,"id":"Q3670558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$ED1BAFC1-8902-4A89-9268-85CAF93D7EC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b4f81716b6b99b3385ea9ee884bdf2887fe5b7","datavalue":{"value":{"entity-type":"item","numeric-id":4721658,"id":"Q4721658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$82CA2784-1ADF-4025-A4A4-B077AD173439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac6746c85a669097b515fb2d37dce6f94b8ec7c0","datavalue":{"value":{"entity-type":"item","numeric-id":3777450,"id":"Q3777450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809630$89EC6892-785D-4726-ABB2-32427097781B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d420852bb62fc90aaab8b17b700844ecc123943","datavalue":{"value":{"entity-type":"item","numeric-id":5946382,"id":"Q5946382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07606b47e5d3b4929fec746d9f9cbb64f3aab666","datavalue":{"value":{"amount":"+0.9066147208213806","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":"Q809630$BEAE260A-2592-4778-8CBF-B1544435E8E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cc4ee2c452f12f612c32b8beeaa372d3655a746","datavalue":{"value":{"entity-type":"item","numeric-id":5716966,"id":"Q5716966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07606b47e5d3b4929fec746d9f9cbb64f3aab666","datavalue":{"value":{"amount":"+0.9066147208213806","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":"Q809630$626C5002-D6C4-4CF2-BA7A-4C3BE881A291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7df7e1a6dacf38d69f52326f7b280c20f4dc4f16","datavalue":{"value":{"entity-type":"item","numeric-id":3721847,"id":"Q3721847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6044f5a8bbdfdfe425713336201dc7235bb69d25","datavalue":{"value":{"amount":"+0.8492934703826904","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":"Q809630$8097F427-1C90-4917-B9CF-974021D85886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9a0d527214d6112d33f2581bcb1ce0779deff7e","datavalue":{"value":{"entity-type":"item","numeric-id":4739330,"id":"Q4739330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70ae59ac7460a8e2dd824648b414ce96d9965250","datavalue":{"value":{"amount":"+0.8238989114761353","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":"Q809630$CED1C8FA-AC58-4F5B-B0CB-A7007BACBBA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73d5fe48fcb9b51155c9c0d1c1c10826d2fa3c82","datavalue":{"value":{"entity-type":"item","numeric-id":1189285,"id":"Q1189285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2e88e2badcba9babebdf3d85caf497f4f83b02","datavalue":{"value":{"amount":"+0.8229142427444458","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":"Q809630$EF1926C1-3669-4910-9686-6EA9C5D19357","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_simple_and_fast_incremental_randomized_algorithm_for_computing_trapezoidal_decompositions_and_for_triangulating_polygons"}}}}}