Accurate quantification of genomic relatedness across samples is a fundamental step for a wide range of analyses, but is challenging in large data sets such as the UK Biobank due to issues such as low density of markers and large sample size. I will present two new methods (ASMC and FastSMC) that enable to very efficiently estimating the time to most recent common ancestor (TMRCA) along the genome of a pair of genotyped individuals. We used ASMC and FastSMC to analyze relatedness using the genomes of 487,409 British individuals from the UK Biobank, with the goal of studying the landscape of genetic relatedness in the UK during the past two millennia. We looked for loci with unusually high density of low TMRCA, aiming to detect recent positive selection. We detected several genome-wide significant signals, including loci with previous evidence of positive selection (including LCT, HLA and TLR) and several novel loci (including the STAT4 autoimmune disease locus). We also applied ASMC to sequencing data from 498 Dutch individuals to detect background selection at deeper time scales. We observed highly significant correlations between average TMRCA inferred by ASMC and other measures of background selection (e.g. McVicker B-statistic, r = -0.28; nucleotide diversity, r = 0.50). We investigated whether this signal translated into an enrichment in disease and complex trait heritability by analyzing summary association statistics from 20 independent diseases and complex traits (86k samples on average) using stratified LD-score regression. Our background selection annotation based on average TMRCA was strongly enriched for heritability (p = 7×10-153) in a joint analysis conditioned on a broad set of functional annotations (including other background selection annotations), meta-analyzed across traits; SNPs in the top 20% of our annotation were 3.8x enriched for heritability compared to the bottom 20%. These results underscore the widespread effects of natural selection on genetic relatedness and on the heritability of disease and complex traits in the human genome.