9.3.4.1. Выпуклая оболочка и дефицит выпуклости

Выше мы определили выпуклое множество как множество, содержащее каждый отрезок прямой, соединяющий две его точки. Выпуклая оболочка Н произвольного множества S есть наименьшее выпуклое множество, содержащее S. Если множество 5 выпуклое с самого начала, то, конечно, H=S. Если множество S содержит только одну связную компоненту, то Н можно представить себе

как множество, ограниченное резиновой лентой, натянутой по периметру множества 5. Разность множеств H—S называется дефицитом выпуклости D множества 5. На рис. 9.16 дефицит выпуклости множества S показан в виде заштрихованной области. Очевидно, что любое множество полностью определяется его выпуклой оболочкой и дефицитом выпуклости. Причина, по которой мы рассматриваем эти множества в описаниях объектов, заключается в том, что они часто позволяют разделить естественным образом сложный объект на несколько менее сложных частей. Например, если читатель поставит задачу описать на английском языке множество S на рис. 9.16, он может с успехом ее решить, описав сначала выпуклую оболочку, а потом обе части дефицита выпуклости. Естественным образом можно получить дальнейшее разделение объекта, заметив, что компоненты всякого дефицита выпуклости распадаются на два различных вида: компоненты, лежащие на границе выпуклой оболочки, и компоненты, заключенные в множество 5. За неимением лучшего термина эти два вида компонент иногда называют заливами и озерами. На рис. 9.16 часть Di ёсть залив, а часть Di — озеро. Заливы и озера объекта могут быть описаны их номером, приблизительным положением относительно объекта и в общем любыми средствами, имеющимися для описания объектов. Таким образом, описание объекта может состоять из описания его выпуклой оболочки, которая обычно проще, чем сам объект, а также его озер и заливов.

Мы должны здесь упомянуть, что расширение понятия выпуклости на дискретные объекты требует некоторой осторожности. Трудности связаны с тем обстоятельством, что, если дан выпуклый аналоговый объект, его квантованный образ в общем случае не выпуклый. Квантованный круг, например, имеет ступенчатую границу и, таким образом, не попадает в число выпуклых. Простой и понятный способ решения этой задачи заключается в следующем: натянуть резиновую ленту вокруг квантованного объекта и считать, что дефицит выпуклости включает только те элементы фона, которые полностью лежат внутри резиновой ленты. Если дефицит выпуклости пуст, тогда, конечно, объект (квантованный) считается выпуклым. Грубо говоря, эти определения сводятся к заданию некоторого допуска, который следует учитывать до того, как относить дискретный объект к числу невыпуклых.