This is much easier than it sounds using a meshgrid and scikit's KNeighborsClassifier.

import numpy as np, matplotlib.pyplot as plt

from sklearn.neighbors.classification import KNeighborsClassifier

from sklearn.datasets.base import load_iris

from sklearn.manifold.t_sne import TSNE

from sklearn.linear_model.logistic import LogisticRegression

# replace the below by your data and model

iris = load_iris()

X,y = iris.data, iris.target

X_Train_embedded = TSNE(n_components=2).fit_transform(X)

print X_Train_embedded.shape

model = LogisticRegression().fit(X,y)

y_predicted = model.predict(X)

# replace the above by your data and model

resolution = 100 # 100x100 background pixels

X2d_xmin, X2d_xmax = np.min(X_Train_embedded[:,0]), np.max(X_Train_embedded[:,0])

X2d_ymin, X2d_ymax = np.min(X_Train_embedded[:,1]), np.max(X_Train_embedded[:,1])

xx, yy = np.meshgrid(np.linspace(X2d_xmin, X2d_xmax, resolution), np.linspace(X2d_ymin, X2d_ymax, resolution))

# approximate Voronoi tesselation on resolution x resolution grid using 1-NN

background_model = KNeighborsClassifier(n_neighbors=1).fit(X_Train_embedded, y_predicted)

voronoiBackground = background_model.predict(np.c_[xx.ravel(), yy.ravel()])

voronoiBackground = voronoiBackground.reshape((resolution, resolution))

plt.contourf(xx, yy, voronoiBackground)

plt.scatter(X_Train_embedded[:,0], X_Train_embedded[:,1], c=y)

plt.show()

You should precisely plot your decision boundary, this will just give you an estimate of roughly where the boundary should lie. It will draw a line between two data points belonging to different classes but will place it in the middle.

Hope this answer helps.