Consegui melhorar o desempenho (reduzir em 30% o tempo de execução) trocando LinkedList por HashMap e reduzindo a representação dos segmentos para apenas os extremos. Mas ainda preciso do LinkedList para desenhar os segmentos. O próximo passo é remover essa dependência.
Terceira versão submetida para avaliação (com runtime melhorado).