The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant and deadlock-free routing algorithms in mesh-connected multicomputers. The convexity of a rectangle facilitates simple and efficient ways to route messages around fault regions using relatively few or no virtual channels to avoid deadlock. However, such a faulty block may include many non-faulty nodes which are disabled, i.e., they are not involved in the routing process. Therefore, it is important to de.ne a fault region that is convex and, at the same time, to include a minimum number of non-faulty nodes. In this paper, we propose an optimal solution that can quickly construct a set of minimum faulty polygons, called orthogonal convex polygons, from a given set of faulty blocks in a 2-D mesh (or 2-D torus). The formation of orthogonal convex polygons is implemented using either a centralized or distributed solution. Both solutions are based on the formation of faulty components each of which consists of adjacent faulty nodes only, followed by the addition of a minimum number of non-faulty nodes to make each component a convex polygon. This provides a solution to an open problem raised in [15]. Extensive simulation has been done to determine the number of non-faulty nodes included in the polygon, and the result obtained is compared with the best existing known result. Results show that the proposed approach can not only find a set of minimum faulty polygons but also does so quickly in terms of the number of rounds of information exchanges and updates between neighbors in the distributed solution.