The precise characterization of the linkage disequilibrium (LD) landscape from high-density single-nucleotide polymorphism (SNP) data underpins the association mapping of diseases and other studies. We describe the algorithm and implementation of a powerful approach for constructing LD genetic maps with meaningful map distances. The computational problems posed by the enormous number of SNPs typed in the HapMap data are addressed by developing segmental map construction with the potential for parallelization, which we are developing. There is remarkably little loss of information (1-2%) through this approach, but the computation times are dramatically reduced (more than fourfold for sequential map assembly). These developments enable the construction of very high-density genome-wide LD maps using data from more than 3 million SNPs in HapMap. We anticipate that a whole-genome LD map will be useful for disease gene mapping, genomic research, and population genetics.