Given a finite set Ex = {Ex1,Ex2,..., ExM} in the plane and a forbidden region ℛ, we want to find a point X ∉ int(ℛ), such that maxMm=1 {wmγm(X – Exm)} is minimized. This is a variant of the well-known continuous Center Problem, where we measure the distance with polyhedral gauges. The unit ball of a polyhedral gauge may be any convex polyhedron containing the origin in its interior. This large class of distance functions allows very general (practical) settings – such as asymmetry – to be modeled. Each Exm is allowed to have its own gauge γm and the forbidden region ℛ enables us to include negative information (which means defining the infeasible region explicitly instead of the feasible region) in the model. Efficient algorithms and structural properties for this non-convex optimization problem based on combinatorial and geometrical methods are presented. A classification scheme for location problems is also introduced.