Minkowski sum is a fundamental operation in many geometric applications, including robotics, penetration depth estimation, solid modeling, and virtual prototyping. However, due to its high computational complexity and several nontrivial implementation issues, computing the exact boundary of the Minkowski sum of two arbitrary polyhedra is generally a difficult task. In this work, we propose to represent the boundary of the Minkowski sum approximately using only points. Our results show that this point-based representation can be generated efficiently. An important feature of our method is its straightforward implementation and parallelization. We also demonstrate that the point-based representation of the Minkowski sum boundary can indeed provide similar functionality as meshbased representations can. We show several applications in motion planning, penetration depth approximation and modeling. An implementation of the proposed method can be obtained from our project webpage at: http://www.cs.gmu.edu/~jmlien/mksum/