PVS isn't that expensive to compute. Especially nowadays. I assume this is actually referring to the binary space partitioning techniques used in DOOM and improved in Quake, Half-Life, etc in the late 90s, early 2000s.

The BSP tree was also extremely useful for optimizing netcode for games like Quake 3 Arena and games within that family and time period I believe.