Число целочисленных точек

[Профессор Снэйп]

С рисунком, конечно, всё очень наглядно и просто. Но если бы переменных было больше, чем $2$, то рисунок был бы уже невозможен. А между тем "аналитический" метод позволяет решать подобные задачи для произвольного конечного числа переменных.

[ewert]

В том или ином смысле "рисунок" всё равно нужен, т.к. здесь важна топология пересечений участков границы.

[Профессор Снэйп]

ewert в сообщении #233257 писал(а):

...топология пересечений участков границы.

А что это такое?

[ewert]

Профессор Снэйп в сообщении #233299 писал(а):

А что это такое?

Не знаю, но -- знаю, что нужна.

Кстати, наиболее простой способ машинного подсчёта -- это просто тупой перебор всех целочисленных точек с отбраковкой тех, которые не удовлетворяют ограничениям (полный аналог ручного подсчёта по картинке на плоскости). Казалось бы, способ неэффективный, но это ещё как сказать. Манипуляции с целыми частями всё равно подразумевают перебор по всем переменным, кроме одной, т.е. порядка $n^{d-1}$ операций, где $n$ -- количество точек по каждой переменной и $d$ -- размерность задачи. А прямой перебор требует порядка $n^d$ операций, не так уж и намного больше. Зато логика программы -- безумно проще.

[Sonic86]

А в общем случае тоже перебором считать
Мне товарищи программисты сообщили такой прикольный факт:
Площадь многоугольника, все вершины которого расположены в точках целочисленной решетки, выражается числом $m+\frac{n}{2}-1$, где $m$ - количество точек решетки, находящихся внутри многоугольника, а $n$ - количество точек решетки, лежащих на границе.
Может это как-то пригодится?

[maxal]

Sonic86 в сообщении #233349 писал(а):

Площадь многоугольника, все вершины которого расположены в точках целочисленной решетки, выражается числом $m+\frac{n}{2}-1$, где $m$ - количество точек решетки, находящихся внутри многоугольника, а $n$ - количество точек решетки, лежащих на границе.

Это т.н. Теорема Пика.
Но здесь она неприменима (по крайней мере в лоб), так как вершины не являются целочисленными.

[vvvv]

А вот и рисунок


-- Чт авг 06, 2009 23:55:46 --

Профессор Снэйп в сообщении #233255 писал(а):

С рисунком, конечно, всё очень наглядно и просто. Но если бы переменных было больше, чем $2$, то рисунок был бы уже невозможен. А между тем "аналитический" метод позволяет решать подобные задачи для произвольного конечного числа переменных.

Если n=3, то вместо прямых линий будут плоскости.

[Профессор Снэйп]

vvvv в сообщении #233420 писал(а):

Если n=3, то вместо прямых линий будут плоскости.

А если $n=4$?

[vvvv]

Профессор Снэйп в сообщении #233434 писал(а):

vvvv в сообщении #233420 писал(а):

Если n=3, то вместо прямых линий будут плоскости.

А если $n=4$?

Да, но Вы сказали " а если n больше двух", вот я и высказался насчет n=3

[ewert]

И вообще, TOTAL умолял только о двух...

[Circiter]

2ewert

Цитата:

Кстати, наиболее простой способ машинного подсчёта -- это просто тупой перебор всех целочисленных точек с отбраковкой тех, которые не удовлетворяют ограничениям (полный аналог ручного подсчёта по картинке на плоскости). Казалось бы, способ неэффективный, но это ещё как сказать.

Набросал на C наикривейший (но все-таки быстрый) brute-force алгоритмик подсчета целочисленных точек в произвольном гиперпространственном полиэдре, заданным набором неравенств (de-facto сканируется пересечение полиэдра с фиксированным положительным гиперкубом):

#include <stdio.h>

/* Auxiliary definitions. */
#define Begin_System             \
    int Inequality               \
    (int Number, int *x)         \
    {switch(Number){
#define End_System               \
    default: printf("Error!");   \
    return 0;}}
#define Entry(n) case n: return

/* Space dimension. */
#define Inequalities 2

/*
**  Size of the scan area
**  (side of the hypercube).
*/
const Cube=100;

/*
**  System of inequalities.
**
**  To add inequality use syntax
**    Entry(<inequality number>) inequality;
**
**  All variables stored in
**  zero-based array x.
*/
Begin_System
    Entry(0) x[1] >= 2*x[0]-4;
    Entry(1) x[1] <= -3*x[0]+40-3*x[1];
End_System

/*
**  Generates next integer point.
*/
int NextPoint(int *Vector)
{
    int Counter=0;

    do
        if(Vector[Counter]==Cube)
            Vector[Counter]=0;
        else
        {
            Vector[Counter]++;
            return 1;
        }
    while(++Counter<Inequalities);

    return 0;
}

int main(void)
{
    int
        Vector[Inequalities]={0},
        Counter,
        IntegerFlag,   
        Result=0;

    printf("Scanning...\n");

    /*
    **  Scan through the hypercube and
    **  count integer points satisfying
    **  inequalities defined above
    **  (i.e. points inside polyhedra,
    **  defined by this conditions).
    */
    do
    {
        for
            (
                Counter=0,IntegerFlag=1;
                Counter<Inequalities;
                Counter++
            )
                if(!Inequality(Counter,Vector)) IntegerFlag=0;
        if(IntegerFlag) Result++;
    }
    while(NextPoint(Vector));

    printf
        (
            "Count of integer points "
            "in given polyhedra is %d.",
            Result
        );

    return 0;
}

В данном случае, эта программулька решает исходную задачу, поставленную LaraKroft. Кстати, ответ равен 41.

-- Вт авг 11, 2009 05:30:20 --

Только что до меня дошло, что этот код может работать не только с многогранниками, но и вообще с любыми ограниченными телами, задающимися системами неравенств (необязательно линейных). Эти области могут быть и невыпуклыми и даже многосвязными.

Цитата:

Манипуляции с целыми частями всё равно подразумевают перебор по всем переменным, кроме одной, т.е. порядка $n^{d-1}$ операций, где $n$ -- количество точек по каждой переменной и $d$ -- размерность задачи. А прямой перебор требует порядка $n^d$ операций, не так уж и намного больше.

Можно сканировать область прыгающими по целочисленной сетке параллельными прямыми исходя из соображения о том, что пересечение области с прямой суть набор отрезков, по длинам и смещениям которых можно подсчитывать целые точки.

В этом случае сложность будет порядка $n^2Q$, где $Q$ -- оценка сложности определения пересечений прямой с границей области. Улучшение асимптотического поведения алгоритма будет наблюдаться если детектирование пересечений будет значительно дешевле чем $n^{d-2}$, но даже при максимальной сложности можно ожидать прироста производительности если хотя бы детектировать за константное время промахи трассировки мимо обмеряемой области.

-- Вт авг 11, 2009 05:51:40 --

Наткнулся на родственную соседнюю тему Как посчитать количество целых точек в многограннике? Там есть интересные ссылочки.

[Circiter]

Ещё несколько слов по поводу мной ранее упомянутого сканирования параллельными прямыми. Что если сканировать тело не параллельными лучами, а под произвольными углами, получая (подсчитывая) искомые точки методами геометрической томографии? Есть смутные (очень смутные) подозрения о том, что это позволит подсчитывать целочисленные точки гораздо более эффективно (быстрее). Кроме того можно попробовать привлечь мат. аппарат интегральной геометрии (ну это уже совсем смутные мыслишки).

Вопрос возник у меня в общем: Есть ли какое-нибудь практическое значение подсчета узлов решеток с натянутыми на них телами (точнее говоря, оценки "объема" пересечения многообразия $\mathcal{P}$ с пространством $\mathbb{Z}^d$). Вроде бы это используется в целочисленной оптимизации/программировании, правда я не в курсе. Может это как-то позволит оценивать объем многомерных многообразий более надежно и быстрее чем через вероятностный Монте-Карло? Или ещё какие-то задачи (прикладные) решать можно таким образом?