# Determine border points of a cluster

My question is as follow. Imagine a random shape cluster of high dimension in an euclidian space, how can i get points which are at the edge of the cluster where edge are defined as segments connecting outermost points.

I can imagine to compute the similarity matrix and get points which are the most distant from others in average, unfortunately with this approach i can't be sure to get all points which are distributed homogeneously across the edge.

I can also try to use a defined parameter to fix a distance where the average distance points are considered to be part of the edge, but it needs a fine tuning which i want to prevent.

• The convex hull approach suits you or tou have too many dimensions to make it practical?
– Evil
Aug 1, 2017 at 20:27
• I don t want the hull, but get points which are in the cluster. Yes i have many dimension. The convex hull is made from existing points or created with virtual points ?
– KyBe
Aug 1, 2017 at 20:33
• I understood that you have points from sone cluster and the edge is the hull of given cluster. The question was to tell apart convex and concave hull, but now it makes me wonder how do you define edge? In the hull there are only existing points from given set (your cluster here).
– Evil
Aug 1, 2017 at 20:48
• Here i will define edge as the successive lines between most external points of the cluster which surrounded all others internal points.
– KyBe
Aug 1, 2017 at 20:52
• The distant points approach will fail with concave shapes. How many dimensions do you have? By consecutive lines do you mean artificial ones or segments connecting outermost points? Do you need to represent lines with more points (possibly at equal intervals)? Could you edit your question to include clarifications?
– Evil
Aug 1, 2017 at 21:22