Является ли это законным использованием reinterpret_cast, и если нет, то как мне это сделать?

Прямого пути нет, потому что constness не распространяется через указатели. В const PointSet сами указатели являются const, а не объекты, на которые они указывают. И, как вы уже выяснили, const Point * — это тип, отличный от Point *, поэтому std::set<const Point *> — это тип, отличный от std::set<Point *>.

Мне не нравится reinterpret_cast структуры STL. Это страшно для меня. STL выполняет всевозможные оптимизации в зависимости от типа параметров шаблона. std::vector<bool> является крайним примером. Вы могли бы подумать, что std::set<T *> и std::set<const T *> будут расположены одинаково, потому что они оба являются указателями, но я бы так не считал, пока не прочитал это в Стандарте.

Если бы это была структура, которую я написал сам, и я мог бы легко убедиться, что актерский состав будет работать, это было бы менее страшно, но все равно уродливо.

Вы можете написать класс-оболочку, который содержит ссылку на std::set<Point *>, но разрешает const доступ только к Points, на который он указывает, через итераторы. Если указатели гарантированно не null, ваш итератор может напрямую разыменовать точки. Я написал это здесь в качестве шаблона:

template <typename T>
class PointerSetViewer
{
public:
    PointerSetViewer(std::set<T *> const &set) : set(set) {}

    struct iterator : public std::iterator<std::forward_iterator_tag, T const>
    {
        iterator(typename std::set<T *>::const_iterator it) : it(it) {}
        T const &operator*() const { return **it; }
        T const *operator->() const { return *it; }
        iterator &operator++() { ++it; return *this; }
        bool operator==(iterator other) { return it == other.it; }
        bool operator!=(iterator other) { return it != other.it; }
    private:
        typename std::set<T *>::const_iterator it;
    };

    iterator begin() { return iterator(set.cbegin()); }
    iterator end() { return iterator(set.cend()); }

private:
    std::set<T *> const &set;
};

Он громоздкий, но он достигает ваших целей, не делая ничего рискованного:

float GetMinimumRangeWrong(PointerSetViewer<Point> &pointSet)
{
    PointerSetViewer<Point>::iterator first(pointSet.begin());
    first->m_x = 42.0f;            // does not compile
}

Кроме того, если вы используете С++ 11, вы можете получить несколько хороших циклов for на основе диапазона:

template <typename T>
PointerSetViewer<T> view_set(std::set<T *> const &set) {
    return PointerSetViewer<T>(set);
}

for (Point const &p : view_set(myPointSet)) {
    // whatever...
}

Барокко? Да, но если один фрагмент кода вычурной библиотеки позволяет написать 100 фрагментов красивого кода приложения с улучшенной проверкой типов, это, вероятно, того стоит.

Редактировать: это не работает для множества. Как указано в комментариях, неконстантный set определен для хранения const T, поэтому на самом деле мы ничего не можем сделать.

На данном этапе я не вижу жизнеспособного решения, кроме как заставить PointSet_ фактически правильно обернуть set, то есть сделать set закрытым и быть осторожным в ваших публичных функциях.

Вот решение, которое я придумал; заставьте set содержать небольшую оболочку, которая будет распространять const себя на указатель.

Я бы подумал, что уже существует класс, который делает это, но ни один из классов умных указателей std, похоже, этого не делает.

#include <iostream>
#include <set>

template<typename T>
struct qualifier_ptr
{
    T *operator->() { return ptr; }
    T const *operator->() const { return ptr; }

    operator T*() { return ptr; }
    operator T const*() const { return ptr; }

    qualifier_ptr(T *p): ptr(p) {}

private:
    T *ptr;
};

struct Point
{
    float m_x;
    float m_y;
};

struct PointSet
{
    typedef std::set< qualifier_ptr<Point> > SetType;
    SetType points;

    float foo() const
    {
        //Point *p = *points.begin();               // error
        Point const *p = *points.begin();           // OK
        return 0;
    }
};

int main()
{
    PointSet ps;
    PointSet const &cps = ps;
    ps.foo();    // OK
    cps.foo();   // OK
}

Обычно я не люблю использовать операторы преобразования, но здесь это кажется уместным.

Как вы указали в комментариях, набор создается только один раз за сеанс, я бы предложил просто создать ConstPointerSet, сделав копию:

void test()
{
    PointSet myPointSet;    
    // Add some points to my set
    ConstPointSet myConstPointSet{ begin(myPointSet), end(myPointSet) };

    float minimumRange1(GetMinimumRange(myConstPointSet));
}

Или оберните его в функцию:

ConstPointSet toConst(const PointSet& pSet){
    return ConstPointSet{ cbegin(pSet), cend(pSet) };
}

Если вам не нужна семантика набора, я бы рекомендовал вместо этого использовать std::vector, который гораздо эффективнее копировать или перемещать.