The specifications for emptyNavigableSet and emptyNavigableMap do not mention what comparator is used. The comparator is visible in the specification via the SortedSet/Map.comparator() method. It is also copied into a newly constructed Set/Map via overloaded constructors of TreeSet/TreeMap. This seems like a hole in the specification.

The implementations use 'null' as the comparator, which can get copied to other instances, leading to odd edge cases. For example:

class Foo { } // not Comparable
NavigableSet<Foo> set1 = Collections.emptyNavigableSet();
set1.comparator();
    // ==> null
NavigableSet<Foo> set2 = new TreeSet<>(set1);
set2.add(new Foo());
    // ==> ClassCastException

The specification should probably say that the Comparator is null, implying natural ordering, and mention the possibility of ClassCastException in these cases.

In some sense the methods should have been declared

    <K extends Comparable<? super K>, V> NavigableMap<K, V> emptyNavigableMap()
    <E extends Comparable<? super E>> NavigableSet<E> emptyNavigableSet()

That probably can't be retrofitted compatibly at this point. New methods could be added, however, it's not clear it's worth it.

A possible extension would be to add a Comparator parameter:

    <K, V> NavigableMap<K, V> emptyNavigableMap(Comparator<? super K> c)
    <E> NavigableSet<E> emptyNavigableSet(Comparator<? super E> c)