Largest empty rectangle (original) (raw)
In computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane. There are a number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain (type of obstacles), and the orientation of the rectangle. The problems of this kind arise e.g., in electronic design automation, in design and verification of physical layout of integrated circuits.
| Property | Value |
|---|---|
| dbo:abstract | In computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane. There are a number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain (type of obstacles), and the orientation of the rectangle. The problems of this kind arise e.g., in electronic design automation, in design and verification of physical layout of integrated circuits. A maximal empty rectangle is a rectangle which is not contained in another empty rectangle. Each side of a maximal empty rectangle abuts an obstacle (otherwise the side may be shifted outwards, increasing the empty rectangle). An application of this kind is enumeration of "maximal white rectangles" in image segmentation R&D of image processing and pattern recognition. In the contexts of many algorithms for largest empty rectangles, "maximal empty rectangles" are candidate solutions to be considered by the algorithm, since it is easily proven that, e.g., a maximum-area empty rectangle is a maximal empty rectangle. (en) Задача о наибольшем пустом прямоугольнике или задача о максимальном пустом прямоугольнике — это задача поиска прямоугольника максимального размера, который следует разместить среди препятствий на плоскости. Существует несколько вариантов задачи, в зависимости от особенностей формулировки, в частности, от способов измерения «размера», области (типы препятствий) и ориентации прямоугольника. Задачи такого вида возникают, например, задачах в автоматизации проектирования электроники, в разработке и проверке интегральных схем. Максимальный пустой прямоугольник (МПП) — это прямоугольник, который не содержит другой пустой прямоугольник. Каждая сторона МПП граничит с препятствием (в противном случае сторону можно было бы сдвинуть, увеличивая пустой прямоугольник). Приложение такого рода задач — перечисление «максимальных белых прямоугольников» в сегментации изображений при и распознавании образов. В контексте многих алгоритмов поиска наибольших пустых прямоугольников «максимальные пустые прямоугольники» являются кандидатами в решение, поскольку легко показать, например, что пустой прямоугольник наибольшей площади является максимальным пустым прямоугольником. (ru) Зада́ча про найбі́льший поро́жній прямоку́тник — це задача пошуку прямокутника найбільшого розміру, який можна розмістити серед перешкод на площині. Існує кілька варіантів задачі, що відрізняються особливостями формулювання, зокрема, від способів вимірювання «розміру», типів перешкод і орієнтації прямокутника. Задачі такого виду виникають, наприклад, в автоматизації проєктування електроніки, в розробці та перевірці компонування інтегральних схем. Найбі́льший поро́жній прямоку́тник (НПП) — це прямокутник, який не міститься в іншому порожньому прямокутнику. Кожна сторона НПП межує з перешкодою (в іншому випадку сторону можна було б зсунути, збільшуючи порожній прямокутник). Такого роду задачі виникають при перерахуванні «найбільших білих прямокутників» у сегментації зображень під час обробки зображень і розпізнавання образів. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Maximum_Empty_Rectangle.png?width=300 |
| dbo:wikiPageID | 23268017 (xsd:integer) |
| dbo:wikiPageLength | 6634 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032237057 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Electronic_design_automation dbr:Cuboid dbr:Integrated_circuit dbc:Geometric_algorithms dbr:Computational_geometry dbr:Pattern_recognition dbr:Time_complexity dbr:Largest_empty_sphere dbr:Isothetic_polygon dbr:Image_segmentation dbr:Rectangle dbr:Minimum_bounding_box dbr:Minimum_bounding_rectangle dbr:Voronoi_diagram dbr:Image_processing dbr:Axis-oriented dbr:Largest_empty_circle dbr:Physical_layout dbr:File:Maximum_Empty_Rectangle.png |
| dbp:wikiPageUsesTemplate | dbt:Redirect dbt:Reflist |
| dct:subject | dbc:Geometric_algorithms |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 |
| rdfs:comment | In computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane. There are a number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain (type of obstacles), and the orientation of the rectangle. The problems of this kind arise e.g., in electronic design automation, in design and verification of physical layout of integrated circuits. (en) Задача о наибольшем пустом прямоугольнике или задача о максимальном пустом прямоугольнике — это задача поиска прямоугольника максимального размера, который следует разместить среди препятствий на плоскости. Существует несколько вариантов задачи, в зависимости от особенностей формулировки, в частности, от способов измерения «размера», области (типы препятствий) и ориентации прямоугольника. Задачи такого вида возникают, например, задачах в автоматизации проектирования электроники, в разработке и проверке интегральных схем. (ru) Зада́ча про найбі́льший поро́жній прямоку́тник — це задача пошуку прямокутника найбільшого розміру, який можна розмістити серед перешкод на площині. Існує кілька варіантів задачі, що відрізняються особливостями формулювання, зокрема, від способів вимірювання «розміру», типів перешкод і орієнтації прямокутника. Задачі такого виду виникають, наприклад, в автоматизації проєктування електроніки, в розробці та перевірці компонування інтегральних схем. (uk) |
| rdfs:label | Largest empty rectangle (en) Задача о наибольшем пустом прямоугольнике (ru) Задача про найбільший порожній прямокутник (uk) |
| owl:sameAs | freebase:Largest empty rectangle yago-res:Largest empty rectangle wikidata:Largest empty rectangle dbpedia-ru:Largest empty rectangle dbpedia-uk:Largest empty rectangle https://global.dbpedia.org/id/4ptwK |
| prov:wasDerivedFrom | wikipedia-en:Largest_empty_rectangle?oldid=1032237057&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Maximum_Empty_Rectangle.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Largest_empty_rectangle |
| is dbo:wikiPageRedirects of | dbr:Maximal_empty_rectangle dbr:Maximum_empty_rectangle dbr:Largest_rectangle |
| is dbo:wikiPageWikiLink of | dbr:Proximity_problems dbr:List_of_combinatorial_computational_geometry_topics dbr:Largest_empty_sphere dbr:Maximal_empty_rectangle dbr:Maximum_empty_rectangle dbr:Minimum_bounding_rectangle dbr:Largest_rectangle |
| is foaf:primaryTopic of | wikipedia-en:Largest_empty_rectangle |
