I have come across a proof where a certain function ("compute a straight skeleton") is shown to take $\Omega(n \log n)$ time by reducing the problem of sorting to it. The overhead for the reduction itself is linear, thus negligible.
Now my question is: is this a valid argument?
The original proof appears in: Huber - Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice, page 19, last paragraph.
In summary:
Given a list of $n$ natural numbers, the author constructs a "Polygon with holes" $P$ of structural size $O(n)$ in linear time. The algorithm then computes a straight skeleton $S(P)$, which can be traversed to enumerate the original numbers in sorted order (with constant overhead per number). Thus, the problem of sorting is reduced to computing $S(P)$. The author claims that this implies computing $S(P)$ is in $\Omega(n \log n)$ due to the bound for sorting.
It is well know that comparison-based sorting algorithms have $\Omega(n \log n)$ worst-case bounds. However, there are $O(n)$ sorting algorithms such as radix sort or bucket sort which aren't based on comparisons and for which this restriction doesn't apply. As far as I can tell, these are all restricted to certain domains, such as fixed-length integers or strings.
I assume generalizing these algorithms to unrestricted domains would reveal hidden costs. If we consider arbitrary integers, some operations which are assumed to be constant cost would actually be logarithmic in the size of the integer. I don't know, however, if this necessarily has to be the case for all possible sorting algorithms.
I think the author's construction could be used for sorting real numbers (possibly requiring a variable-length encoding), if this strengthens the requirement on the sorting enough to rule out any $O(n)$ (or $o(n \log n)$) sorting algorithms.
Are there any information theoretic arguments showing that, for fully general inputs and all operations strictly accounted for, at least $\Omega(n \log n)$ basic units of work (whether they be comparison or something else) are always needed? If not, does that mean the argument of "by reduction from sorting" doesn't strictly prove a lower bound stronger than $\Omega(n)$?
