  We propose a new approach to explore the neutral-current non-standard
neutrino interactions (NSI) in atmospheric neutrino experiments using
oscillation dips and valleys in reconstructed muon observables, at a detector
like ICAL that can identify the muon charge. We focus on the flavor-changing
NSI parameter $\varepsilon_{\mu\tau}$, which has the maximum impact on the muon
survival probability in these experiments. We show that non-zero
$\varepsilon_{\mu\tau}$ shifts the oscillation dip locations in $L/E$
distributions of the up/down event ratios of reconstructed $\mu^-$ and $\mu^+$
in opposite directions. We introduce a new variable $\Delta d$ representing the
difference of dip locations in $\mu^-$ and $\mu^+$, which is sensitive to the
magnitude as well as the sign of $\varepsilon_{\mu\tau}$, and is independent of
the value of $\Delta m^2_{32}$. We further note that the oscillation valley in
the ($E$, $\cos \theta$) plane of the reconstructed muon observables bends in
the presence of NSI, its curvature having opposite signs for $\mu^-$ and
$\mu^+$. We demonstrate the identification of NSI with this curvature, which is
feasible for detectors like ICAL having excellent muon energy and direction
resolutions. We illustrate how the measurement of contrast in the curvatures of
valleys in $\mu^-$ and $\mu^+$ can be used to estimate $\varepsilon_{\mu\tau}$.
Using these proposed oscillation dip and valley measurements, the achievable
precision on $|\varepsilon_{\mu\tau}|$ at 90% C.L. is about 2% with 500
kt$\cdot$yr exposure. The effects of statistical fluctuations, systematic
errors, and uncertainties in oscillation parameters have been incorporated
using multiple sets of simulated data. Our method would provide a direct and
robust measurement of $\varepsilon_{\mu\tau}$ in the multi-GeV energy range.
