{"entities":{"Q1088412":{"pageid":1099164,"ns":120,"title":"Item:Q1088412","lastrevid":69613647,"modified":"2026-04-13T08:12:50Z","type":"item","id":"Q1088412","labels":{"en":{"language":"en","value":"Constructing maximal slicings from geometry"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3990891"}},"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":"Q1088412$714D7802-45CD-4786-9CCA-A162907D8A81","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8e475daea435de3a987ae2558b0df437f60bfd6a","datavalue":{"value":{"text":"Constructing maximal slicings from geometry","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1088412$CBF87673-D2E3-4FA7-8A7A-B98D552680C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed576079652308b41e8a20f6e2dfba02a43137e4","datavalue":{"value":"0612.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088412$03EE23DF-6F48-4B78-A2F1-EC0446A2107F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ef2e4f3a8eb13d7aac800c88854890fa39820546","datavalue":{"value":"10.1007/BF00289114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088412$1479D094-7816-41ED-9108-8248B6362A32","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088412$0D511685-84E8-410C-9F0C-4A5F99189DA9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088412$3F020794-8035-4E75-8AD9-A6ECC2245C8B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1088412$D823FFC7-8ECE-413C-88B8-B428EE3CF679","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b64e9c813320d4b8a00c375734e83ec4212631d1","datavalue":{"value":"We present an optimal algorithm to determine whether a placement of N isothetic non-overlapping rectangles (macros) can be represented by a slicing tree, and if so, to find a representation of minimal height. A slicing is a recursive partition of the overall bounding rectangle, by straight horizontal or vertical cuts, into rectangular regions, each one containing exactly one macro. The algorithm first determines a representation of the empty space of the placement by means of maximally extended horizontal and vertical channels. A second phase then generates a maximal slicing tree (an ordered tree with unbounded degree and maximal branching, i.e., minimal height) in a top-down fashion. The complexity of each phase is O(N log N). The problem arises in steps (1) and (2) of our top-down approach to VLSI custom chip design, which consists of (1) floorplanning by slicing, (2) hierarchicial global wiring, and (3) detailed layout of macros.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088412$AB5E0E4A-5754-4E69-8E96-664BB5890DA2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088412$8025D158-D4E1-43C5-84B6-371A0E4A35FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088412$C7D48887-2D6A-4278-9947-94E00F1C6828","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd2e51e5f49d2811fa46e6b55f1365542ac9ebfd","datavalue":{"value":"3990891","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088412$F87A2896-2C77-4E06-8716-2F866EF62989","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"803e88858831f9854eacd0d87951d07ace6dd1a8","datavalue":{"value":"isothetic non-overlapping rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088412$BC755F0D-16BE-4A54-9B6A-3695F5DE55F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7371ae1a2199039b5b7396c98e8f3e4509a526c","datavalue":{"value":"macros","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088412$852FA492-11D3-48A1-946D-472684C63144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f1a86a1f9f187af003630a50b5fd9ac186d6e32","datavalue":{"value":"maximal slicing tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088412$897937DE-53B8-4879-AA6E-6EBB2519FADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4f6fc8be8069b141ef8e03be09f893a555224c6","datavalue":{"value":"VLSI custom chip design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088412$EA61A50A-6828-47EC-B13E-FDDDB43BC911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e234a4ae5027457881d3519feaf671345045aa84","datavalue":{"value":"floorplanning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088412$55C3151F-8693-4858-86A1-6E909B1A01A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb2b14dfe24ae4858c91618a626add315c11d362","datavalue":{"value":"hierarchicial global wiring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088412$9A935233-6B03-4D99-8A29-84E5ACEA75B8","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":"Q1088412$01D80AEB-BABF-4B29-986E-6CB017B8182A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"77da926e59fb910cfb7ee736e14bf3a1c85b9513","datavalue":{"value":{"entity-type":"item","numeric-id":3709924,"id":"Q3709924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088412$629A22B5-9A00-49D8-AD8D-89DB648885F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"362ecc334bf34b43e6b23bfb9924ff2b0f8eba1d","datavalue":{"value":{"entity-type":"item","numeric-id":3334981,"id":"Q3334981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088412$5D517B23-6E9C-483F-8450-97FF3F3D8810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fcfe987d8cbbd43f7b7238b024d7a85de33a069","datavalue":{"value":{"entity-type":"item","numeric-id":3936212,"id":"Q3936212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088412$A1C82765-1199-423E-BB20-623DA97BCDC7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"59ee4df993d10d66e03ecb6477dd8534fdd47540","datavalue":{"value":"https://doi.org/10.1007/bf00289114","type":"string"},"datatype":"url"},"type":"statement","id":"Q1088412$A9987FFB-13A9-4887-869D-51F16BA937BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6b595d2357487337ca609d3e669b96ff86364df5","datavalue":{"value":"W1967860513","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088412$71314435-B3D2-4B48-A30D-75440A659C7E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1903f0e30888f2d3089ab1e045bb46605e486a3e","datavalue":{"value":{"entity-type":"item","numeric-id":1700125,"id":"Q1700125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33b687ee9ff33c459d1b6ced6613cb65fc4bce81","datavalue":{"value":{"amount":"+0.8792447","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":"Q1088412$0D4B7705-876A-49C1-83C2-302F9FC15852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aae73b3cd271a0b300d2b5e641c66a6868670ca8","datavalue":{"value":{"entity-type":"item","numeric-id":2851765,"id":"Q2851765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bdbad750349128f2fee841aafac952450b74f2f","datavalue":{"value":{"amount":"+0.87125766","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":"Q1088412$5BF9BF30-ADEA-479F-AC2D-6CA89C2603F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fb35d7103ad9bc48f5edb7001c2fe5b00761526","datavalue":{"value":{"entity-type":"item","numeric-id":3319425,"id":"Q3319425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"493940f92c717ead333339435ad418213d2e6319","datavalue":{"value":{"amount":"+0.85392666","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":"Q1088412$D9310053-805A-48EE-BFB2-2C76A89D8135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cdb49276828cae2b9a6ecb1209b12f4f7f76c5e","datavalue":{"value":{"entity-type":"item","numeric-id":4880215,"id":"Q4880215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"577ea339a3c6a4ff61561aaf170c8a67e5f26ce2","datavalue":{"value":{"amount":"+0.8505907","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":"Q1088412$B1C9C6AF-303B-425B-AE2F-82964CC65E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbaf1bd276484e78d8442d3233ddd9f20ec04382","datavalue":{"value":{"entity-type":"item","numeric-id":2482200,"id":"Q2482200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f97dd0973ed7694c0ba57387d9c68034ab3c6f21","datavalue":{"value":{"amount":"+0.84704816","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":"Q1088412$82536B16-116C-451A-BC8E-4D099580E171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4419e44b3fa064cd48a007cbd12295b4964ba93f","datavalue":{"value":{"entity-type":"item","numeric-id":3619933,"id":"Q3619933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f97dd0973ed7694c0ba57387d9c68034ab3c6f21","datavalue":{"value":{"amount":"+0.84704816","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":"Q1088412$89322B7F-AF41-4ECF-820B-73A3165B929F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbdc1e202fd03f06524d23ed0818ecd82d1d7d50","datavalue":{"value":{"entity-type":"item","numeric-id":4494726,"id":"Q4494726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d708298beab15dc429c10404c02e1a85a8fa0d0","datavalue":{"value":{"amount":"+0.84641963","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":"Q1088412$33097CB5-676D-4BC2-932E-668574FF8BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bae7d03cde1564a60bbc3bed14c268a3b6d05aa","datavalue":{"value":{"entity-type":"item","numeric-id":5902168,"id":"Q5902168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5806aa1779c7f1323202ead4adf005e45e4ec32d","datavalue":{"value":{"amount":"+0.84182346","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":"Q1088412$DB491A6D-13A4-48F9-B0B6-2404BB9EE811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"790f386009601c3adda64c1583aa4d2532b14698","datavalue":{"value":{"entity-type":"item","numeric-id":5906765,"id":"Q5906765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5806aa1779c7f1323202ead4adf005e45e4ec32d","datavalue":{"value":{"amount":"+0.84182346","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":"Q1088412$81268F38-BBB2-442E-9100-A46E8CD1AA82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b821ad54d7234395aeba856e991abfb4e0e14a5","datavalue":{"value":{"entity-type":"item","numeric-id":3083325,"id":"Q3083325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82eb197328d683e84f38ea645a8b1d903e6afb56","datavalue":{"value":{"amount":"+0.83333576","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":"Q1088412$C677DD20-E1F6-44FF-B66E-52B3912EA36F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Constructing maximal slicings from geometry","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Constructing_maximal_slicings_from_geometry"}}}}}