0
$\begingroup$

I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$?

There are methods like convex hull, concave hull and $\alpha$-hull, which produce boundary points, provided we know the nature of the set (i.e. whether it is convex or concave).

But I have lots of sets with different sizes and I need boundary points for each of the set. So it is not convenient to know the nature of each set. Rather, I need a method which will give the boundary points of each set without prior specification of the nature of the sets.

Any suggestion or reference will be greatly appreciated.

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ What is the boundary of a finite set? $\endgroup$
    – Alex Degtyarev
    Commented Nov 3, 2014 at 17:47
  • $\begingroup$ Suppose we plot the finite set of points on X-Y plane and suppose these points form a cluster. Then by boundary points of the set I mean the boundary point of this cluster of points. That is if we connect these boundary points with piecewise straight line then this graph will enclose all the other points. For example, i.sstatic.net/hwxSW.jpg here points on the red curve are the boundary points. $\endgroup$
    – janak
    Commented Nov 3, 2014 at 19:07
  • 2
    $\begingroup$ OK, but what's the definition? Something that would make the red curve better than any other curve? $\endgroup$
    – Alex Degtyarev
    Commented Nov 3, 2014 at 19:12
  • $\begingroup$ It is a polygon which embraces all the points, but has minimal area. $\endgroup$
    – janak
    Commented Nov 3, 2014 at 19:24
  • 5
    $\begingroup$ Not good: if you don't require convexity or such, minimal area tends to $0$: just take a polygonal neighborhood of a tree. The reason why I keep asking is that, if you give a right definition, the answer would probably be obvious (at least, for a finite set). $\endgroup$
    – Alex Degtyarev
    Commented Nov 3, 2014 at 20:08

2 Answers 2

Reset to default
2
$\begingroup$

What you want is computational topology, which is a rapidly growing field, and there is a good (which is not the same as "easy") book by Edelsbrunner and Harer.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ I'm not sure how anything in EH answers the question (I have the book in front of me). Did you have any specific part of the book in mind? $\endgroup$
    – Vidit Nanda
    Commented Nov 3, 2014 at 17:52
  • $\begingroup$ This is as good an application of persistent homology as there ever was, and "image segmentation" might be the most appropriate part of EH. $\endgroup$
    – Igor Rivin
    Commented Nov 3, 2014 at 17:55
  • $\begingroup$ @IgorRivin How does image segmentation and/or persistence identify the boundary in any sense of a planar point set? One might get a one-parameter family of partitions of these points, but it isn't clear how that would help with the problem at hand. $\endgroup$
    – Vidit Nanda
    Commented Nov 3, 2014 at 21:08
  • $\begingroup$ I was thinking of alpha shapes-type things, like so: people.mpi-inf.mpg.de/~jgiesen/tch/sem06/Celikik.pdf $\endgroup$
    – Igor Rivin
    Commented Nov 3, 2014 at 21:55
2
$\begingroup$

I suggest you explore curve reconstruction via local feature size. The following figure is essentially an "algorithm without words":

DCGFig5.9
  (Figure from Discrete and Computational Geometry.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ @janak: :-) ${}$ $\endgroup$
    – Joseph O'Rourke
    Commented Nov 5, 2014 at 20:48

Not the answer you're looking for? Browse other questions tagged .