1
$\begingroup$

This question is an extension of a previous question I've asked.

Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (We have to check each point to know its kind).

Assume that somehow we know that the points of kind 1 (and so the points of kind 2) form a connected region (i.e. , 1s and 2s are not scattered in the plane arbitrarily). Given the condition of being of kind 1 or 2, The goal is to find the region occupied by 1s (a search problem). Consider somehow we know the following attributes of the region occupied by 1s: (one at a time)

  1. The region occupied by 1s forms a convex set (so it is 1-connected too). enter image description here

2.The region occupied by 1s forms a simply connected region , but not necessarily convex.

enter image description here

The simplest algorithm for finding the region of 1s is to simply start from bottom of the rectangle and sweep it and check all of the points in the rectangle to determine their kind and this way find the region.This is not an efficient algorithm, because we can use the known fact of convexity (or simply-connectivity) of the region of 1s to find it more easily without inspecting all of the points.

What more efficient algorithms are there to find the region , as fast as possible? (with an acceptable accuracy, which is about 0.001 in my work). The regions may have sharp edges. But their detection is limited to the mentioned accuracy too. (It is clear that finding the boundary of the region suffices)

Please don't forget that the problem is to find an unknown set of points, not bound a known set of points. i.e., it's a search problem , not a convex hull finding problem.

(also, speed is very important for me)

EDIT1:

After some suggestions (in the comments) I should say that I think we can take advantage of simply-connectivity of the region to write an algorithm that tries to find the boundary of the region instead of checking more points to find the region directly.

$\endgroup$
  • $\begingroup$ As I added now in the question, this is a search problem, not finding the convex hull problem. 1-connected means simply connected. My input is the set of points in the rectangle, that to each of them corresponds a 1 or 0 (a YES or a NO, if you prefer); and my goal is to find the region occupied by 1s. $\endgroup$ – user215721 May 28 '13 at 22:18
  • $\begingroup$ As the problem is now, it is unclear. What is the input? If the input is a matrix with points, this can be achieved (optimally?) by DFS. $\endgroup$ – Pål GD May 28 '13 at 22:35
  • 2
    $\begingroup$ I second @PålGD. What's wrong with just finding an arbitrary 1-point, and starting a standard graph traversal from there? Are you already solving the problem with some algorithm? $\endgroup$ – Juho May 28 '13 at 22:56
  • 2
    $\begingroup$ @user215721 The algorithm is asymptotically optimal, meaning that you can only do better by a constant factor using some other algorithm. And no, in the worst case every point is a $1$. You still have to check every one to determine this. In practice, you might be able to come up with something slightly better. Try to think if there's something more you might know about the input. "No holes" is a good start at least. $\endgroup$ – Juho May 28 '13 at 23:36
  • 2
    $\begingroup$ @user215721 Or how about this: start from a corner and move towards the center. Halt when you find a first $1$. Start a DFS from that point. When choosing where to move, only pick a neighbor that has a $0$ neighbor. This guarantees(?) you stay at the boundary while moving. Keep going until you build a cycle and come back to the vertex you started from. Would this work? This might be bit better in practice, depending on what the inputs look like. $\endgroup$ – Juho May 28 '13 at 23:43
2
$\begingroup$

Here's an idea that might be quick in practice. Judging from the OP's comments, this is idea is implementable.

The idea is that we start scanning from a corner and approach the center of the rectangle. Once the scan finds a vertex $v$ with label $1$, it halts. Start a DFS from $v$. Keep a stack $F$ that represents the frontier into which you can expand the search. A vertex is put into the stack if and only if it has at least one neighbor whose label is $0$. The idea is to complete a cycle, while staying on the boundary. enter image description here

The figure above is a rough representation of the initial region of the green vertices labeled $1$. Say we start scanning from the upper right corner. The vertex $29$ is the one we hit, and the one from which we start a DFS. enter image description here

The DFS was started from the purple vertex $29$. In the figure, $F$ would contain $9$ and $28$, because they are the only neighbors we can visit next that have at least one neighbor with the label $0$. The cycle is completed when we come back to $29$ or when the frontier meets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.