\section{Introduction}
\label{introsection}

SIM Lite is currently expected to have $\sim$80 spectral channels \citep{SIM09}, spanning 450 to 900 nm, thus allowing multi-wavelength microarcsecond astrometry, which no current or planned ground or space-based astrometric project, (GAIA, CHARA, VLT/PRIMA, etc.) is able to match. We showed in our first paper \citep{Coughlin10}, hereafter referred to as Paper I, the implications multi-wavelength microarcsecond astrometry has for interacting binary systems. In this paper, we discuss an interesting effect we encountered while modeling binary systems, namely that gravity darkening in stars produces a wavelength dependent astrometric offset from the center of mass that increases with decreasing wavelength. It is possible to use this effect to derive both the inclination and gravity darkening exponent of a star in certain cases.

Determining the absolute inclination of a given star has many practical applications. There is much interest in the formation of binary stars, where whether or not the spin axis of each star is aligned with the orbital axis provides insight into the formation history of the system \citep{Turner95}. The mutual inclination between the stellar spin axes and orbital axis can greatly affect the rate of precession, which is used to probe stellar structure and test general relativity \citep{Sterne39a,Sterne39b,Sterne39c,Kopal59,Jeffery84}. \citet{Albrecht09} recently reconciled a 30-year-old discrepancy between the observed and predicted precession rate of DI Herculis through observations which showed the stellar spin axes were nearly perpendicular to the orbital axis. Along similar lines, extrasolar planets discovered via the radial velocity technique only yield the planetary mass as a function of the inclination of the orbit \citep{Mayor95, Noyes97, Marcy00}, and thus, if one assumes the planetary orbit and stellar rotation axes are nearly parallel, determining the absolute inclination of the host star yields the absolute mass of the planet. If the stellar spin axis is found not to be parallel to the planetary orbital axis, this provides valuable insights into the planet's formation, migration, and tidal evolution histories \citep{Winn06,Fabrycky09}. A final example is the study of whether or not the spin axes of stars in clusters are aligned, which both reveals insight into their formation processes, as well as significantly affects the determination of the distances to those clusters \citep{Jackson10}.

Our proposed technique can also be used in conjunction with other methods of determining stellar inclination to yield more precise inclination values and other stellar parameters of interest. \citet{Gizon03} and \citet{Ballot06} have shown that one can derive the inclination of the rotation axis for a given star using the techniques of astroseismology given high-precision photometry with continuous coverage over a long baseline, such as that provided by the CoRoT and Kepler missions. This technique is sensitive to rotation rates as slow as the Sun's, but becomes easier with faster rotation rates. \citet{Domiciano04} discuss how spectro-interferometry can yield both the inclination angle and amount of differential rotation for a star, parameterized by $\alpha$. For both eclipsing binaries and transiting planets, the observation of the Rossiter-McLaughlin (RM) effect can yield the relative co-inclination between the two components \citep{Winn06,Albrecht09,Fabrycky09}. The technique we propose in this paper would be complementary to these techniques in several ways. First, it would provide an independent check on the derived inclination axis from each method, confirming or refuting the astroseismic models and spectro-interferometric and RM techniques. Second, in principle the astroseismic technique is not dependent on the gravity darkening coefficient $\beta_{1}$, and the spectro-interferometric technique is correlated with the value for $\alpha$; combining techniques would yield direct and robust observationally determined values for $i$, $\alpha$, and $\beta_{1}$. Finally, the accurate, observational determination of $\alpha$ and $\beta_{1}$, (along with stellar limb-darkening), is critical to accurately deriving the co-inclination from the RM effect, as well as other quantities in stellar and exoplanet astrophysics.

In this paper, we also present models for and discuss the determination of spot location, temperature, and size on single stars, which produce a wavelength-dependent astrometric signature as they rotate in and out of view. Star spots are regions on the stellar surface where magnetic flux emerges from bipolar magnetic regions, which blocks convection and thus heat transport, effectively cooling the enclosed gas, and thus are fundamental indicators of stellar magnetic activity and the internal dynamos that drive it. \citet{Isik07} discuss how the observation of spot location, duration, stability, and temperature can probe the stellar interior and constrain models of magnetic flux transport. Through the observation of the rotation rates of starspots at varying latitudes, one is able to derive the differential rotation rate of the star \citep{Collier02}, which may be directly related to the frequency of starspot cycles. Mapping spots in binary star systems provides insight into the interaction between the magnetic fields of the two components, which can cause orbital period changes \citep{Applegate92}, radii inflation \citep{Lopez-Morales07,Morales08}, and may possibly explain the $\sim$2-3 hour period gap in cataclysmic variable systems \citep{Watson07}. Detecting and characterizing star spots via multi-wavelength astrometry would be complementary to other existing techniques, namely optical interferometry \citep{Wittkowski02}, tomographic imaging \citep{Donati06,Auriere08}, photometric monitoring \citep{Alekseev04,Mosser09}, and in the future, microlensing \citep{Hwang10}.

We present the details of our modeling code, \textsc{reflux}, in \S\ref{refluxsection}, discuss the inclination effect and present models for multiple stars in \S\ref{incsection}, discuss the spot effects and present models in \S\ref{spotsection}, and present our conclusions in \S\ref{conclusionsection}.

\section{The {\sc reflux} Code}
\label{refluxsection}

\textsc{reflux}\footnotemark[1] is a code that computes the flux-weighted astrometric reflex motion of binary systems. We discussed the code in detail in Paper I, but in short, it utilizes the Eclipsing Light Curve (ELC) code, which was written to compute light curves of eclipsing binary systems (Orosz \& Hauschildt 2000). The ELC code represents the surfaces of two stars as a grid of individual luminosity points, and calculates the resulting light curve given the provided systemic parameters. ELC includes the dominant physical effects that shape a binary's light curve, such as non-spherical geometry due to rotation, gravity darkening, limb darkening, mutual heating, reflection effects, and the inclusion of hot or cool spots on the stellar surface. For the work in this paper we have simply turned off one of the stars, thus allowing us to probe the astrometric effects of a single star. To compute intensity, ELC can either use a blackbody formula or interpolate from a large grid of NextGen model atmospheres (Hauschildt et al. 1999). For all the simulations in this paper, we have used the model atmosphere option, and will note now, and discuss more in detail later, that the calculation of limb-darkening is automatically included in NextGen model atmospheres. These artificially derived limb-darkening coefficients have recently been shown to be in error by as much as $\sim$10-20\% in comparison to observationally derived values \citep{Claret08}, and thus their uncertainties must be included, although for this work, due to symmetry, we find the introduced error is negligible. For all our simulations, we model the U, B, V, R, I, J, H, and K bands for completeness and comparison to future studies, though we note that SIM Lite will not be able to observe in the U, J, H, or K bandpasses.

\footnotetext[1]{\textsc{reflux} can be run via a web interface from \url{http://astronomy.nmsu.edu/jlcough/reflux.html}. Additional details as to how to set-up a model are presented there.}

\section{Inclination and Rotation}
\label{incsection}

The astrophysical phenomenon of gravity darkening, also sometimes referred to as gravity brightening, is the driving force behind the ability to determine the inclination of a single star using multi-wavelength astrometry. A rotating star is geometrically distorted into an oblate spheroid, such that its equatorial radius is greater than its polar radius, and thus the poles have a higher surface gravity, and the equator a lower surface gravity, than a non-rotating star with the same mass and average radius. This increased surface gravity, $g$, at the poles results in a higher effective temperature, T$_{\rm eff}$, and thus luminosity; decreased $g$ at the equator results in a lower T$_{\rm eff}$ and luminosity. This temperature and luminosity differential causes the star's center of light, or photocenter, to be shifted towards the visible pole, away from the star's gravitational center of mass. Since the inclination determines how much of the pole is visible, the amount of displacement between the photocenter and the center of mass is directly related to the inclination. Furthermore, since the luminosity difference effectively results from a ratio of blackbody luminosities of differing temperatures, the effect is wavelength dependent, with shorter wavelengths shifted more than longer wavelengths. Thus, the amount of displacement between the measured photocenter in two or more wavelengths is directly related to the inclination. See Figure~\ref{incfig} for an illustration of the effect.

\begin{figure*}
\centering
\begin{tabular}{cc}
\epsfig{file=f1a.eps, width=0.474\linewidth} &
\epsfig{file=f1b.eps, width=0.474\linewidth} \\
\end{tabular}
\caption{Illustration of the inclination effect using brightness maps of Capella Ab, which has an inclination of 42.788$\degr$ \citep{Torres09}. Left: Capella Ab artificially spun-up to near its break-up speed, to accentuate the gravity darkening effect for ease of viewing. As can be seen, the photocenter of the system is dramatically shifted away from the center of mass, towards the visible pole, which is brighter than the rest of the star due to gravity darkening. Furthermore, since the pole is physically hotter, the U-band photocenter is shifted more than the K-band photocenter, and in the direction of the projected rotation axis, or y-axis. Right: Capella Ab at its actual rotation period. As can be seen, the actual effect is small compared to the angular size of the star on the sky, but still large compared to the 1 $\mu$as benchmark of SIM Lite. The presence of gravity darkening is clearly visible, which causes a decrement in flux towards the limb of the star. Note that the broad wavelength covereage of SIM Lite will only cover the B, V, R, and I bandpasses.}
\label{incfig}
\end{figure*}

An additional complicating factor is the exact dependence of temperature on local gravity. \citet{Zeipel24} was the first to derive the quantitative relationship between them, showing that $T_{\rm eff}^{4} \propto g^{\beta_{1}}$, where $\beta_{1}$ is referred to as the gravity darkening exponent. The value of $\beta_{1}$ has been a subject of much study and debate; for a complete review, see \citet{Claret00}, who presents both an excellent discussion of past studies, as well as new, detailed computations of $\beta_{1}$ using modern models of stellar atmospheres and internal structure that encompass stars from 0.08 to 40 M$_{\sun}$. Since the value of $\beta_{1}$ affects the temperature differential between equator and pole, the multi-wavelength displacement will also be dependent on the value of $\beta_{1}$. The total amplitude of the effect will be scaled by the angular size of the star, which depends on both its effective radius and distance. Thus, in total, the components of this inclination effect are the effective stellar radius, distance, effective temperature, rotation rate, $\beta_{1}$, and inclination of the star. In principle, one is able to determine the effective stellar radius, effective temperature, rotation rate, and distance of a target star using ground-based spectroscopy and space-based parallax measurements, including from SIM Lite. Thus, when modeling the multi-wavelength displacement of the stellar photocenter, the only two components that need to be solved for are the inclination and $\beta_{1}$, with $\beta_{1}$ already having some constraints from theory.

A good trio of stars for modeling and testing this inclination effect are the components of the binary system Capella, (Aa and Ab), and the single star Vega. \citet{Torres09} has very recently published an extremely detailed analysis of both the binary orbit of Capella and the physical and evolutionary states of the individual components, providing both new observations, as well as drawing from the previous observations and analyses of \citet{Hummel94} and \citet{Strassmeier01}. Vega, in addition to being one of the most well-studied stars in the sky, has recently been discovered to be a very rapid rotator seen nearly pole-on \citep{Aufdenberg06,Peterson06,Hill10}. In total, these three stars represent both slow and rapid rotators for giant and main-sequence stars at a range of temperatures, as Capella Aa is a slow-rotating K-type giant, Capella Ab is a fast-rotating G-type giant, and Vega is a very fast-rotating A-type main-sequence star. With many ground-based interferometric observations to compare with, and being bright and nearby, these stars also present excellent targets for SIM Lite.

We use the \textsc{reflux} code to generate models of the astrometric displacement from \emph{U}-band to \emph{H}-band, with respect to the \emph{K}-band photocenter, for inclinations from 0 to 90$\degr$, for each star, as shown in Figures~\ref{CapellaAaFig},~\ref{CapellaAbFig}, and~\ref{VegaFig}. We use systemic parameters given by \citet{Torres09} for Capella Aa and Ab, and by \citet{Aufdenberg06} and \citet{Peterson06} for Vega, listed in Tables~\ref{CapellaAaTable},~\ref{CapellaAbTable}, and~\ref{VegaTable} respectively. We employ the model atmospheres incorporated into the ELC code, as well as automatically chosen values for $\beta_{1}$ based on Figure 1 of \citet{Claret00}. Additionally, in each figure we show a dashed line to indicate the effect of decreasing the gravity darkening coefficient by 10\% to simulate the uncertainty of the models \citep{Claret00} and explore the correlation with other parameters.

\begin{figure}
\centering
\epsfig{file=f2.eps, width=\linewidth}
\caption{The astrometric displacement of each bandpass with respect to \emph{K}-band versus inclination for Capella Aa. Dashed lines are a model with $\beta _{1}$ decreased by 10\%. Due to the slow rotation rate of Capella Aa, the effect is limited to a maximum of $\sim$2.0 microarcseconds between U and K-band, and only a maximum of $\sim$0.7 $\mu$as between B and I-band, where SIM Lite will operate. This puts the detection of this effect for Capella Aa at the very edge of SIM Lite's capability.}
\label{CapellaAaFig}
\end{figure}

\begin{figure}
\centering
\epsfig{file=f3.eps, width=\linewidth}
\caption{The astrometric displacement of each bandpass with respect to \emph{K}-band versus inclination for Capella Ab. Dashed lines are a model with $\beta_{1}$ decreased by 10\%. Due to the fast rotation rate of a Capella Ab like star, the effect is moderate with tens of microarcseconds of displacement, and thus these types of stars are excellent targets for SIM Lite. The actual inclination of Capella Ab is 42.788$\degr$ \citep{Torres09}, and thus Capella Ab itself should show a large shift of the photocenter with wavelength. Note that the broad wavelength covereage of SIM Lite will only cover the B, V, R, and I bandpasses.}
\label{CapellaAbFig}
\end{figure}

\begin{figure}
\centering
\epsfig{file=f4.eps, width=\linewidth}
\caption{The astrometric displacement of each bandpass with respect to \emph{K}-band versus inclination for Vega. Dashed lines are a model with $\beta_{1}$ decreased by 10\%. Note that due to the very fast rotation of Vega, along with a high value of $\beta_{1}$, the effect can be quite large, at a couple hundred micro-arcseconds. For a Vega-like star, SIM Lite observations would yield very accurate values for $\beta_{1}$ and the inclination. For Vega itself, which is known to be nearly pole on, with an inclination of 5.7$\degr$ \citep{Hill10}, there should be a B-band minus I-band displacement of 6.0 $\mu$as, still detectable by SIM Lite. Note that the broad wavelength covereage of SIM Lite will only cover the B, V, R, and I bandpasses.}
\label{VegaFig}
\end{figure}

\begin{deluxetable}{lc}
\tablewidth{0pt}
\tablecaption{Parameters for Capella Aa}
\tablecolumns{2}
\tablehead{Parameter & Value\tablenotemark{a}}
\startdata
Distance (pc) & 12.9\\
Rotation Period (Days) & 106.0\\
Mass (M$_{\sun}$) & 2.70\\
Radius (R$_{\sun}$) & 12.2\\
Effective Temperature (K) & 4940\\
$\beta_{1}$ & 0.43
\enddata
\label{CapellaAaTable}
\tablenotetext{a}{Values from \citet{Torres09}}
\end{deluxetable}

\begin{deluxetable}{lc}
\tablewidth{0pt}
\tablecaption{Parameters for Capella Ab}
\tablecolumns{2}
\tablehead{Parameter & Value\tablenotemark{a}}
\startdata
Distance (pc) & 12.9\\
Rotation Period (Days) & 8.64\\
Mass (M$_{\sun}$) & 2.56\\
Radius (R$_{\sun}$) & 9.2\\
Effective Temperature (K) & 5700\\
$\beta_{1}$ & 0.39
\enddata
\label{CapellaAbTable}
\tablenotetext{a}{Values from \citet{Torres09}}
\end{deluxetable}

\begin{deluxetable}{lc}
\tablewidth{0pt}
\tablecaption{Parameters for Vega}
\tablecolumns{2}
\tablehead{Parameter & Value\tablenotemark{a}}
\startdata
Distance (pc) & 7.76\\
Rotation Period (Days) & 0.521\\
Mass (M$_{\sun}$) & 2.11\\
Radius (R$_{\sun}$) & 2.5\\
Effective Temperature (K) & 9602\\
$\beta_{1}$ & 1.02
\enddata
\label{VegaTable}
\tablenotetext{a}{Values from \citet{Aufdenberg06} and \citet{Peterson06}}
\end{deluxetable}

As can be seen from these models, we find that the effect is quite large for a Capella Ab-like or Vega-like fast rotator, but only marginally detectable for a slower-rotating system like Capella Aa. This also implies that this effect would not be detectable for a slow-rotating, main-sequence star like our Sun. Our modeling confirms this, showing a total U-K amplitude of $\ll$ 0.1 $\mu$as for a 1.0 M$_{\sun}$, 1.0 R$_{\sun}$ star with a rotation period of 30.0 days at 10.0 parsecs. These conclusions on detectability are made with the assumption that, for bright stars like these, SIM Lite can achieve its microarcsecond benchmark. We show this is possible in narrow angle (NA) mode by employing the SIM Differential Astrometry Performance Estimator (DAPE) \citep{Plummer09}. For a target star with magnitude V$=$5, and a single comparison star with V$=$10 located within a degree of it on the sky, by integrating 15 seconds on the target, and 30 seconds on the reference, for 10 visits at 5 chop cycles each, a final precision of $\pm$1.01 $\mu$as is achieved in only 1.04 hours of total mission time. For a fainter target with $V$=10, this precision is only reduced to $\pm$1.32 $\mu$as in the same amount of mission time. In utilizing NA mode, one must be careful in choosing the reference star(s), to ensure that they are not stars with a substantial wavelength dependant centroid. Given the only constraints on reference stars are that they need to have V $\gtrsim$ 10 and are within one degree on the sky, one could easily choose a slow-rotating, main-sequence star, determined as such via ground-based observations, as a wavelength-independent astrometric reference star. We also note that wide angle SIM Lite measurements, with a precision of $\sim$5 $\mu$as, may not detect the wavelength dependent photoceter of a system like Capella, but will have no difficulty detecting it in stars like Capella Ab or Vega.

The effect of decreasing the gravity darkening exponent is to decrease the total amplitude of the effect in each wavelength, with shorter wavelengths affected more than longer wavelengths. Thus, the choice of gravity darkening exponent is intimately tied to the derived inclination. If one were to model observed data with a gravity darkening exponent that was $\sim$10\% different than the true value, they would derive an inclination that would also be $\sim$10\% different from the true inclination. However, the two combinations of inclination and gravity darkening exponent do not produce identical results, and can be distinguished with a sufficient precision at a number of wavelengths. For example, if one were to adopt the nominal value for $\beta_{1}$ and derive an inclination of 40 degrees for a Vega-like star, then adopt a $\beta_{1}$ value that was 10\% lower, one would derive an inclination of 43 degrees, a 7.5\% change. In this case though, with the lower $\beta_{1}$ value, the measured photocenter in the U, B, V, R, I, J, and H bandpasses, with respect to the K-band photocenter, would differ from the nominal $\beta_{1}$ model by $\sim$0.5, -1.0, -2.0, -2.0, -1.6, -1.0, and 0.2 $\mu$as respectively. Note that for B, V, R, and I, where SIM Lite can observe, these discrepancies, on the order of $\sim$1.0 $\mu$as, should be large enough to be distinguished in NA mode. Thus, a unique solution exists for the values of \emph{i} and $\beta_{1}$ if the photocenter is measured in three or more wavelengths. (The photocenter of one wavelength is used as a base measurement that the photocenters of other wavelengths are measured with respect to, as we have chosen K-band as the base measurement in our models. With the photocenter measured in three or more wavelengths total, there are two or more photocenter difference measurements, with two unknown variables for which to solve.) Another complication is the possibility of having equally good fitting high and low solutions for $\emph{i}$. For example, if one observed and determined a best-fit inclination of 70 degrees for a Vega-like star, one could obtain a reasonably good fit as well at 46 degrees, (see Fig~\ref{VegaFig}). However, just as in the case of the uncertainity in the value of $\beta_{1}$, discernible discrepancies would exist. In this case, the discrepencies in the measured photocenter in the U, B, V, R, I, J, and H bandpasses, with respect to the K-band photocenter, would be $\sim$0.1, -9.0, -2.0, 1.5, 6.0, 1.0, and 0.2 $\mu$as respectively. Just as in the case of the uncertainity in the value of $\beta_{1}$, this discrepancy between equally good fitting high and low inclination solutions can be resolved if one has three or more wavelengths obtained in NA mode.

As mentioned in \S\ref{introsection}, we note that the limb-darkening function, which was automatically chosen by the ELC code as incorporated into the model atmospheres, can differ from actual observed values by $\sim$10\% \citep{Claret08}. We have tested how changing the limb-darkening coefficients by 10\% affects the resulting astrometric displacements, and find that the result is less than 0.5\% for all wavelengths, and thus is negligible in the modeling. The reason is that limb-darkening is symmetric, and thus while increased limb-darkening damps the visible pole, it also damps the rest of the star, and thus the relative brightness between regions is maintained.

Additionally, this inclination technique yields the orientation of the projected stellar rotation axis on the sky, which is parallel to the wavelength dispersion direction. When coupled with the derived inclination, this technique thus yields the full 3-dimensional orientation of the rotation axis. This could be a powerful tool in determining the overall alignment of stellar axes in the local neighborhood and in nearby clusters.

\section{Star Spots}
\label{spotsection}

Another area of astrophysical interest to which multi-wavelength astrometric measurements from SIM Lite can contribute is the study of star spots. As the cause of star spots are intense magnetic fields at the photosphere, they are typically found in stars with convective envelopes, especially rapidly rotating stars. Thus, both low-mass, main-sequence K and M dwarfs, as well as rapidly rotating giant and sub-giant stars, are known to host large spots on their surface. The study of the distribution, relative temperature, and size of these spots would greatly contribute to the study of magnetic field generation in stellar envelopes. A starspot that rotates in and out of view will cause a shift of the photocenter for a single star, which has been a subject of much recent discussion in the literature \citep[e.g.][]{Hatzes02,Unwin05,Eriksson07,Catanzarite08,Makarov09,Lanza08}, especially in light of its potential to mimic, or introduce noise when characterizing, an extrasolar planet. However, there has been no mention in the literature of the multi-wavelength astrometric signature of stellar spots, where, just as in the case of the gravity darkening inclination effect, we are looking at essentially two blackbodies with varying temperatures, and thus shorter wavelengths will be more affected by a spot than longer wavelengths.

To characterize the multi-wavelength astrometric signature of stellar spots, we model two spotty systems, again using the {\sc reflux} code. We model Capella Ab, which shows evidence of large spots and is suspected of being a RS CVn variable \citep{Hummel94}, and a typical main-sequence K dwarf. For Capella Ab, we use the parameters listed in Table~\ref{CapellaAbTable}, along with the star's determined inclination of 42.788$\degr$ \citep{Torres09}, and add a cool spot that has a temperature that is 60\% of the average surface temperature, located at the equator, at a longitude such that it is seen directly at phase 270$\degr$, and having an angular size of 10$\degr$, (where 90$\degr$ would cover exactly one half of the star). For the K dwarf system, we use the physical parameters listed in Table~\ref{kdwarftable}, simulating a typical K Dwarf at 10 parsecs, and add a cool spot with the same parameters as we do for Capella Ab. Additionally, to investigate the effects of cool versus hot spots or flares, we also run a model with a hot spot by changing the spot temperature to be 40\% greater than the average surface temperature. We present our models in Figures~\ref{CapellaAbSpotFig},~\ref{SingleStarCoolSpot}, and~\ref{SingleStarHotSpot}.

\begin{deluxetable}{lc}
\tablewidth{0pt}
\tablecaption{Parameters for the K Dwarf System}
\tablecolumns{2}
\tablehead{Parameter & Value}
\startdata
Distance (pc) & 10.0\\
Inclination ($\degr$) & 60.0\\
Period (Days) & 20\\
Mass (M$_{\sun}$) & 0.6\\
Radius (R$_{\sun}$) & 0.6\\
Effective Temperature (K) & 4500\\
Latitude of Spot ($\degr$) & 90\\
Longitude of Spot ($\degr$) & 270\\
Angular Size of Spot ($\degr$) & 10\\
Cool Spot Temperature Factor & 0.6\\
Hot Spot Temperature Factor & 1.4
\enddata
\label{kdwarftable}
\end{deluxetable}

\begin{figure*}
\centering
\begin{tabular}{cc}
\epsfig{file=f5a.eps, width=0.45\linewidth} &
\epsfig{file=f5b.eps, width=0.45\linewidth} \\
\end{tabular}
\caption{A simulated cool Spot on CapellaAb. The spot is located on the equator, with a longitude such that it is seen directly at phase 270$\degr$. The strong presence of the gravity darkening effect, discussed in \S\ref{incsection}, dominates the wavelength spread in the y direction. Note that the broad wavelength covereage of SIM Lite will only cover the B, V, R, and I bandpasses.}
\label{CapellaAbSpotFig}
\end{figure*}

\begin{figure*}
\centering
\begin{tabular}{cc}
\epsfig{file=f6a.eps, width=0.45\linewidth} &
\epsfig{file=f6b.eps, width=0.45\linewidth} \\
\end{tabular}
\caption{A simulated cool spot on a nearby K dwarf star with an inclination of 60$\degr$, whose parameters are given in Table~\ref{kdwarftable}. The spot is located on the equator, with a longitude such that it is seen directly at phase 270$\degr$. Note that the broad wavelength covereage of SIM Lite will only cover the B, V, R, and I bandpasses.}
\label{SingleStarCoolSpot}
\end{figure*}

\begin{figure*}
\centering
\begin{tabular}{cc}
\epsfig{file=f7a.eps, width=0.45\linewidth} &
\epsfig{file=f7b.eps, width=0.45\linewidth} \\
\end{tabular}
\caption{A simulated hot spot or flare on a nearby K dwarf star with an inclination of 60$\degr$, whose parameters are given in Table~\ref{kdwarftable}. The spot is located on the equator, with a longitude such that it is seen directly at phase 270$\degr$. Note that the broad wavelength covereage of SIM Lite will only cover the B, V, R, and I bandpasses.}
\label{SingleStarHotSpot}
\end{figure*}

As can be seen for CapellaAb, the gravity darkening inclination effect presented in \S\ref{incsection} dominates the spread of colors in the y-direction, the direction parallel to the stars' projected rotation axis. However, the amplitude of the spot motion is quite large, with a total amplitude of $\sim$40 $\mu$as in all bandpasses, which would be easily detectable by SIM Lite. For the K dwarf with a cool spot, we see a much smaller, but still detectable shift of amplitude $\sim$5-8 $\mu$as, depending on the wavelength. In the case of a hot spot or flare, we see a much larger displacement, on the order of $\sim$10-200 $\mu$as, depending on the wavelength, which would be easily detectable by SIM and provide extremely precise values in deriving the spot parameters.

In general, the temperature of the spot, in relation to the mean stellar surface temperature, is related to the spread in observed wavelengths, with a larger spread indicating a larger temperature difference. The duration of the astrometric displacement in phase, coupled with the overall amplitude of the astrometric displacement, yields the size of the spot, as larger spots will cause larger displacements and be visible for a larger amount of rotational phase. The latitude of the spot can also affect the total duration. Finally, the amplitude of the astrometric displacement in the x versus the y direction is dependent on both the latitude of spot as well as the inclination of the star. Thus, when modeled together, one is able to recover these parameters. This work can also be combined with our work in Paper I to derive the location of spots in binary systems, as the astrometric signature of the spot is simply added to the astrometric signature of the binary system.

The astrometric motion induced upon a parent star by a host planet does not have a wavelength dependence. Spots however, as we have shown via our modeling, have a clear wavelength dependence. Thus, if one has a candidate planetary signal from astrometry, but it shows a wavelength-dependant motion, it must then be a false positive introduced from star spots at the rotation period of the star, (assuming that the planet's emitted flux is negligible compared to the star.) Furthermore, when SIM is launched, there will likely be many cases where a marginally detectable signal due to a planetary companion is found at a very different period than the rotation period of the star. However, starspots will still introduce extra astrometric jitter which will degrade the signal from the planetary companion. Multi-wavelength astrometric data can be used to model and remove the spots, which will have a wavelength dependence, and thus strengthen the planetary signal, which will not have a wavelength dependence.

\section{Discussion and Conclusion}
\label{conclusionsection}

We have presented detailed models of the multi-wavelength astrometric displacement that SIM Lite will observe due to gravity darkening and stellar spots using the \textsc{reflux} code. We find that SIM Lite observations, especially when combined with other techniques, will be able to determine the absolute inclination, gravity darkening exponent, and 3-dimensional orientation of the rotational axis for fast and slow rotating giant stars, and fast-rotating main-sequence stars. This technique will be especially useful in probing binary star and exoplanet formation and evolution, as well as the physics of star forming regions. Direct observational determination of the gravity darkening exponent has direct applications in both stellar and exoplanet astrophysics. This technique is also relatively inexpensive in terms of SIM Lite observing time, as one need only to observe a given star once, as opposed to binary stars and planets, which require constant monitoring over an entire orbit. It should be noted that this effect should be taken into account when constructing the SIM Lite astrometric reference frame, such that fast-rotating giants should be excluded so as not to produce a wavelength-dependent astrometric reference fame.

We also have presented models of star spots on single stars, and find that SIM Lite should be able to discern their location, temperature, and size. Combined with other techniques, this will provide great insight into stellar differential rotation, magnetic cycles and underlying dynamos, and magnetic interaction in close binaries. From this modeling, it should especially be noted that multi-wavelength astrometry is a key tool in the hunt for extrasolar planets, either by ruling out false signals created by spots, or simply removing extra astrometric jitter introduced by spots. Thus, it remains critical that SIM Lite maintains a multi-wavelength astrometric capability in its final design.

\acknowledgments
This work was sponsored in part by a SIM Science Study (PI: D. Gelino) from the National Aeronautics and Space Administration through a contract with the Jet Propulsion Laboratory, California Institute of Technology. J.L.C. acknowledges additional support from a New Mexico Space Grant Consortium Fellowship. We thank the referee for comments which greatly helped to improve this manuscript, particularly in making the presentation of our ideas much clearer.


\section{Introduction}
\label{sec:intro}
In this paper, we study the problem of reconstructing a simple polygon $P$
from the visibility angles measured at the vertices of $P$ and
from the cyclically ordered vertices of $P$ along its boundary.
Precisely, for an unknown simple polygon
$P$ of $n$ vertices, suppose we are given (1) the vertices ordered
counterclockwise (CCW) along the boundary
of $P$, and (2) for each vertex $v$ of $P$, the angles
between any two adjacent rays emanating from $v$ to the vertices of
$P$ that are visible to $v$ such that these angles
are in the CCW order as seen around $v$, beginning
at the CCW neighboring vertex of $v$ on the boundary of $P$ (e.g., see
Fig.~\ref{fig:angles}).
A vertex $u$ of $P$ is {\em visible} to a vertex $v$ of $P$ if the
line segment connecting $u$ and $v$ lies entirely in $P$.
The objective of the problem is to reconstruct the simple polygon $P$ (up
to similarity) that fits all the
given angles. We call this problem the {\em polygon
reconstruction problem from angles}, or {\em PRA} for short.
Figure~\ref{fig:example} gives an example.

\begin{figure}[t]
\begin{minipage}[t]{\linewidth}
\begin{center}
\includegraphics[totalheight=1.2in]{angles.eps}
\caption{\footnotesize Illustrating the angle measurement at a
vertex $v$: The angle sequence $(\alpha_1,\alpha_2,\alpha_3,\alpha_4)$
is given.
}\label{fig:angles}
\end{center}
\end{minipage}
\end{figure}

The PRA\ problem has been studied by Disser, Mihal\'ak, and Widmayer
\cite{ref:DisserRe10}, who showed that the solution polygon
for the input is unique (up to similarity) and gave an $O(n^3\log n)$
time algorithm for reconstructing such a polygon. Using the input,
their algorithm first constructs the visibility graph $G$ of $P$ and
subsequently reconstructs the polygon $P$. As shown in
\cite{ref:DisserRe10}, once $G$ is known, the polygon $P$ can be
obtained efficiently (e.g., in $O(n^2)$ time) with the help of the angle data
and the CCW ordered vertex sequence of $P$.

Given a visibility
graph $G$, the problem of determining whether there is a polygon $P$
that has $G$ as its visibility graph is called the visibility graph
{\em recognition} problem, and the problem of actually constructing
such a polygon $P$ is called the visibility graph {\em reconstruction} problem.
Note that the general visibility graph recognition and reconstruction
problems are long-standing open problems with only partial results known
(e.g., see \cite{ref:AsanoVi00} for a short survey). Everett
\cite{ref:EverettVi90} showed that the visibility graph reconstruction
problem is in PSPACE, but no better upper bound on the complexity of
either problem is known. In our problem setting, we have the
angle data information and the ordered vertex list of $P$; thus
$P$ can be constructed efficiently after knowing $G$.

Hence, the major part of the algorithm in \cite{ref:DisserRe10} is
dedicated to constructing the visibility graph $G$ of $P$.
As indicated in \cite{ref:DisserRe10}, the key difficulty
is that the vertices in this
problem setting have no recognizable labels, e.g., the angle
measurement at a vertex $v$ gives angles between visible vertices to
$v$ but does not identify these visible vertices globally.
The authors in \cite{ref:DisserRe10} also showed that some natural greedy
approaches do not seem to work. An $O(n^3\log n)$ time algorithm for
constructing $G$ is given in \cite{ref:DisserRe10}. The algorithm,
called the {\em triangle witness algorithm}, is based
on the following observation: Suppose we wish to determine whether a
vertex $v_i$ is visible to another vertex $v_j$; then $v_i$ is
visible to $v_j$ if and only if there is a vertex $v_l$ on the portion of
the boundary of $P$ from $v_{i+1}$ to $v_{j-1}$ in the CCW order such
that $v_l$ is visible to both $v_i$ and $v_j$ and the triangle formed
by the three vertices $v_i,v_j$, and $v_l$ does not intersect the
boundary of $P$
except at these three vertices (such a vertex $v_l$ is called a {\em triangle
witness vertex}).

In this paper, based on the triangle witness algorithm
\cite{ref:DisserRe10}, by exploiting some new geometric properties, we
give an improved algorithm with a running time of $O(n^2)$. The
improvement is due to two key observations. First, in the triangle
witness algorithm \cite{ref:DisserRe10}, to determine whether a vertex
$v_i$ is visible to another vertex $v_j$, the algorithm needs to
determine whether there exists a triangle witness vertex along the
boundary of $P$ from $v_{i+1}$ to $v_{j-1}$ in the CCW order; to this
end, the algorithm checks every vertex in that boundary portion of
$P$. We observe that it suffices to check only one particular vertex in that
boundary portion. This removes an $O(n)$ factor from the running time of
the triangle witness algorithm \cite{ref:DisserRe10}. Second, some
basic operations in the triangle witness algorithm
\cite{ref:DisserRe10} take $O(\log n)$ time each; by utilizing certain
different
data structures, our new algorithm can handle each of those
basic operations in constant time.
This removes another $O(\log n)$ factor from the running time. Note that
since the input size is $\Theta(n^2)$ in the worst case (e.g., the
total number of all visibility angles), our algorithm is worst-case optimal.

As shown in \cite{ref:DisserRe10}, if only the angle measurements are
given, i.e., the ordered vertices along the
boundary of $P$ are unknown, then the information is not sufficient for
reconstructing $P$. In other words, it may be possible to compute several simple
polygons that are not similar but all fit the given measured angles (see
\cite{ref:DisserRe10} for an example).

\begin{figure}[t]
\begin{minipage}[t]{\linewidth}
\begin{center}
\includegraphics[totalheight=1.2in]{example.eps}
\caption{\footnotesize The given measured angles are ordered CCW along
the polygon boundary (left); reconstructing a simple polygon that fits these angles (right).
}\label{fig:example}
\end{center}
\end{minipage}
\end{figure}

\subsection{Related Work}

The problems of reconstructing geometric objects based on measurement
data have been studied extensively (e.g.,
\cite{ref:BiedlRe09,ref:BiloRe09,ref:JacksonOr02,ref:SidleskyPo06,ref:SnoeyinkCr99}).
As discussed above, the general visibility graph recognition and
reconstruction problems are in PSPACE \cite{ref:EverettVi90} and no better
complexity upper bound is known so far (e.g., see \cite{ref:EverettNe95}).
Yet, some results have been given for certain special polygons.
For example, Everett and
Corneil \cite{ref:ErerettRe90} characterized the visibility graphs of
spiral polygons and
gave a linear time reconstruction algorithm. Choi, Shin, and Chwa
\cite{ref:ChoiCh95}, and Colley, Lubiw, and Spinrad
\cite{ref:ColleyVi97} characterized and
recognized the visibility graphs of funnel-shaped polygons.

By adding extra information, some versions of the problems become more tractable.
O'Rourke and Streinu \cite{ref:ORourkeTh98} considered the {\em
vertex-edge} visibility graph that includes edge-to-edge visibility
information. Wismath \cite{ref:WismathPo00}
introduced the {\em stab graphs} which are
also an extended visibility structure and showed how parallel line
segments can be efficiently reconstructed from it.
Snoeyink \cite{ref:SnoeyinkCr99} proved that a unique simple
polygon (up to similarity) can be determined by the interior angles at
its vertices and the cross-ratios of the diagonals of any given
triangulation, where the cross-ratio of a diagonal is the product of
the ratios of edge lengths for the two adjacent triangles.
Jackson and Wismath \cite{ref:JacksonOr02} studied the reconstruction
of orthogonal polygons from horizontal and vertical visibility
information and gave an $O(n\log n)$ time reconstruction algorithm.
Biedl, Durocher, and Snoeyink \cite{ref:BiedlRe09} considered the problem of
reconstructing the two-dimensional floor plan of a polygonal room
using different types of scanned data, and proposed several problem models.
Sidlesky, Barequet, and Gotsman
\cite{ref:SidleskyPo06} studied the problem of reconstructing a planar
polygon from its intersections with a collection of
arbitrarily-oriented ``cutting" lines.

Reconstructing a simple polygon from angle data was first
considered by Bil\`o {\em et al}.~\cite{ref:BiloRe09}, who aimed to understand what kinds of
sensorial capabilities are sufficient for a robot moving inside an unknown
polygon to reconstruct the visibility graph of the polygon.
It was shown in \cite{ref:BiloRe09} that if the robot is equipped with a compass
to measure the angle between any two vertices that are
currently visible to the robot
and also has the ability to know where it came from when
moving from vertex to vertex,
then the visibility graph of the polygon
can be uniquely reconstructed. Reconstruction and exploration of environments
by robots in other problem settings have also been studied (e.g.,
see \cite{ref:DudekRo91,ref:FlocchiniTh99,ref:SuriSi08}).

The rest of this paper is organized as follows. In Section \ref{sec:pre}, we
give the problem definitions in detail and
introduce some notations and basic observations.
To be self-contained, in Section \ref{sec:review}, we briefly review the
triangle witness algorithm given in \cite{ref:DisserRe10}.
We then present our improved algorithm in Section \ref{sec:improve}.

\vspace*{-0.10in}
\section{Preliminaries}
\label{sec:pre}
In this section, we define the PRA\ problem in detail and introduce
the needed notations and terminology. For ease of discussion and comparison, some of our
notations follow those in \cite{ref:DisserRe10}.

Let $P$ be a simple polygon of $n$ vertices $v_0,v_1,\ldots,v_{n-1}$ in the CCW
order along $P$'s boundary. Denote by $G=(V,E)$ the visibility graph
of $P$, where $V$ consists of all vertices of $P$ and for any two distinct
vertices $v_i$ and $v_j$, $E$ contains an edge $e(v_i,v_j)$ connecting $v_i$ and
$v_j$ if and only if $v_i$ is visible to $v_j$ inside $P$. In this
paper, the indices of all $v_i$'s are taken as congruent modulo $n$,
i.e., if $n\leq i+j\leq 2n-1$, then $v_{i+j}$ is the same vertex as $v_l$, where
$l= i+j - n$ (or $l= (i+j) \mod n$); similarly, if $-n \leq i-j<0$, then $v_{i-j}$ is the same
vertex as $v_l$, where $l=i-j+n$. For each $v_i\in V$,
denote by $deg(v_i)$ its degree in the visibility graph $G$, and denote by
$vis(v_i)=(vis_1(v_i),vis_2(v_i),\ldots,vis_{deg(v_i)}(v_i))$
the sequence of vertices in $P$ visible to $v_i$ from $v_{i+1}$ to
$v_{i-1}$ ordered CCW around $v_i$. We refer to $vis(v_i)$ as $v_i$'s
{\em visibility angle sequence}.
Note that since both $v_{i-1}$ and $v_{i+1}$ are visible to $v_i$,
$vis_1(v_{i}) = v_{i+1}$
and $vis_{deg(v_i)}(v_i) = v_{i-1}$. For any two vertices $v_i,v_j$ in
$V$, let $ch(v_i,v_j)$ denote the sequence
$(v_i,v_{i+1},\ldots,v_j)$ of the vertices ordered CCW along the
boundary of $P$ from $v_i$ to $v_j$. We refer to
$ch(v_i,v_j)$ as a {\em chain}. Let $|ch(v_i,v_j)|$ denote the
number of vertices of $P$ in the chain $ch(v_i,v_j)$.

For any two distinct vertices $v_i,v_j \in P$, let $\rho(v_i,v_j)$ be the ray emanating from
$v_i$ and going towards $v_j$. For any three vertices $v,v_i,v_j\in P$, denote by
$\angle_v(v_i,v_j)$ the CCW angle defined by rotating
$\rho(v,v_i)$ around $v$ to $\rho(v,v_j)$ ($v_i$ or $v_j$ need not be
visible to $v$). Note that the values
of all angles we use in this paper are in $[0,2\pi)$. For any
vertex $v\in P$ and $1\leq i< j\leq deg(v)$, let $\angle_v(i,j)$ be
$\angle_v(vis_i(v),vis_j(v))$.

The PRA\ problem can then be
re-stated as follows: Given a sequence of all vertices
$v_0,v_1,\ldots,v_{n-1}$ of an unknown simple polygon $P$ in the CCW order along
$P$'s boundary, and the angles $\angle_v(i,i+1)$ for each vertex $v$ of $P$ with
$1\leq i< deg(v)$, we seek to reconstruct $P$ (up to
similarity) to fit all the given angles.
Without loss of generality, we assume that no three distinct vertices of $P$ are collinear.

It is easy to see that after $O(n^2)$ time preprocessing, for any $v\in V$ and any
$1\leq i< j\leq deg(v)$, the angle $\angle_v(i,j)$ can be obtained
in constant time. In the following discussion, we assume that this
preprocessing has already been done. Sometimes we (loosely) say that these
angles are given as input.

The algorithm given in \cite{ref:DisserRe10} does not construct $P$ directly.
Instead, the algorithm first computes its visibility graph $G=(V,E)$.
As mentioned earlier, after knowing $G$, $P$ can be reconstructed efficiently with
the help of the angle data and the CCW ordered vertex sequence of $P$.
The algorithm for constructing $G$ in \cite{ref:DisserRe10} is
called the {\em triangle witness algorithm}, which will be briefly reviewed
in Section \ref{sec:review}.
Since $V$ consists of all vertices of $P$, the
problem of constructing $G$ is equivalent to constructing its edge set
$E$, i.e., for any two distinct vertices $v_i, v_j\in P$,
determine whether there is an edge $e(v_i,v_j)$ in $E$ connecting $v_i$
and $v_j$ (in other words,
determining whether $v_i$ is visible to $v_j$ inside $P$).

To discuss the involved algorithms, we need one more definition.
For any two vertices $v_i,v_j\in P$ with
$|ch(v_{i+1},v_{j-1})|\geq 1$,
suppose a vertex $v_l\in ch(v_{i+1},v_{j-1})$
is visible to both $v_i$ and $v_j$; then we let $v_j'$ be the
{\em first} visible vertex to $v_i$ on the chain $ch(v_j,v_i)$ and let
$v_i'$ be the {\em last} visible vertex to $v_j$ on the chain $ch(v_j,v_i)$
(e.g., see Fig.~\ref{fig:sangle}). Intuitively, imagine that we
rotate a ray from $\rho(v_i,v_l)$ around $v_i$
counterclockwise; then the first vertex on the chain
$ch(v_j,v_i)$ hit by the rotating ray  is $v_j'$.
Similarly, if we rotate a ray from
$\rho(v_j,v_l)$ around $v_j$ clockwise,
then the first vertex on the chain $ch(v_j,v_i)$ hit by
the rotating ray is $v_i'$.
Note that if $v_i$ is visible to $v_j$, then
$v_j'$ is $v_j$ and $v_i'$ is $v_i$.  We denote by
$\angle^{\uparrow}_{v_i}(v_l,v_j)$ the angle $\angle_{v_i}(v_l,v_j')$ and denote
by $\angle^{\uparrow}_{v_j}(v_i,v_l)$ the angle $\angle_{v_j}(v_i',v_l)$. It should be
pointed out that for ease of understanding this paper, the above statement of defining $\angle^{\uparrow}$
is different from that in \cite{ref:DisserRe10} but they refer to the
same angles in the algorithm. The motivation for
defining $\angle^{\uparrow}$ will be clear after discussing the
following lemma, which has been proved in \cite{ref:DisserRe10}.

\begin{figure}[t]
\begin{minipage}[t]{\linewidth}
\begin{center}
\includegraphics[totalheight=1.5in]{sangle.eps}
\caption{\footnotesize Illustrating the definitions of $v'_i$ and
$v_j'$, and $\angle^{\uparrow}_{v_i}(v_l,v_j)$ and
$\angle^{\uparrow}_{v_j}(v_i,v_l)$ which are the angles $\angle_{v_i}(v_l,v_j')$ and
$\angle_{v_j}(v_i',v_l)$, respectively.
}\label{fig:sangle}
\end{center}
\end{minipage}
\end{figure}

\vspace*{-0.07in}
\begin{lemma}\label{lem:10}\cite{ref:DisserRe10}
For any two vertices $v_i,v_j\in P$ with $|ch(v_{i+1},v_{j-1})|\geq 1$,
$v_i$ is visible
to $v_j$ if and only if there exists a vertex $v_l$ on
$ch(v_{i+1},v_{j-1})$ such that $v_l$ is visible to both $v_i$ and
$v_j$ and
$\angle^{\uparrow}_{v_i}(v_l,v_j)+\angle^{\uparrow}_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=\pi$.
\end{lemma}
\vspace*{-0.07in}

Since the above lemma is also critical to our improved algorithm in
Section \ref{sec:improve}, we sketch the proof of the lemma below.

For any two
vertices $v_i,v_j\in P$ with $|ch(v_{i+1},v_{j-1})|\geq 1$, if $v_i$ is visible to
$v_j$, then it is not difficult to see that
there must exist a vertex $v_l\in ch(v_{i+1},v_{j-1})$ that is
visible to both $v_i$ and $v_j$. Since the three vertices
$v_i,v_j$, and $v_l$ are mutually visible to each other, it is clear
that the triangle formed by these three vertices does not intersect the
boundary of $P$ except at the three vertices, implying
that $\angle^{\uparrow}_{v_i}(v_l,v_j)+\angle^{\uparrow}_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=
\angle_{v_i}(v_l,v_j)+\angle_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=\pi$.
Such a vertex $v_l$ is called a {\em triangle witness} of the edge
$e(v_i,v_j)$ in $E$.

Suppose $v_i$ is not visible to $v_j$; then it is possible that there does not
exist a vertex $v_l\in ch(v_{i+1},v_{j-1})$ which is visible
to both $v_i$ and $v_j$. In fact, if there
exists no vertex $v_l\in ch(v_{i+1},v_{j-1})$ that is visible
to both $v_i$ and $v_j$, then $v_i$ cannot be visible to $v_j$. Hence in
the following, we assume that such a vertex $v_l$ exists, i.e., a
vertex $v_l\in
ch(v_{i+1},v_{j-1})$ is visible to both $v_i$ and $v_j$ (yet $v_i$ is not visible to $v_j$).
Note that $v_l$ is not collinear with $v_i$ and $v_j$.
If $\angle_{v_l}(v_j,v_i)>\pi$ (i.e., the chain $ch(v_{i},v_{j})$ is part of the
boundary of $P$ that blocks
the visibility between $v_i$ and $v_j$), then the lemma obviously holds.  Otherwise,
$\angle_{v_l}(v_j,v_i)<\pi$, and in this case,
the visibility between $v_i$ and $v_j$ is blocked
by the chain $ch(v_{j},v_{i})$.
Since $v_i$ is not visible to $v_j$, for any choice of such a vertex $v_l$,
the angle $\angle_{v_i}(v_l,v_j)$
is not given by $v_i$'s visibility angle sequence $vis(v_i)$.
The ``closest approximation" for $\angle_{v_i}(v_l,v_j)$ in this case is determined by
a vertex $v$ on the chain $ch(v_{j},v_{i})$ such that $v$ becomes $v_j$ if and
only if $v_j$ is visible to $v_i$.
As in the definition of
$\angle^{\uparrow}_{v_i}(v_l,v_j)$, the vertex $v_j'$ is such a vertex $v$, i.e., the
first visible vertex to $v_i$ on the chain $ch(v_j,v_i)$.
Similarly, the
vertex $v_i$ in $\angle_{v_j}(v_i,v_l)$ is ``replaced" in the definition
of $\angle^{\uparrow}_{v_j}(v_i,v_l)$ by $v_i'$, i.e.,
the last visible vertex to $v_j$ on $ch(v_j,v_i)$.
Clearly, when $v_j$ is not visible to $v_i$, it must hold that
$\angle_{v_i}(v_l,v_j')<\angle_{v_i}(v_l,v_j)$ and
$\angle_{v_j}(v_i',v_l)<\angle_{v_j}(v_i,v_l)$. Therefore,
$\angle^{\uparrow}_{v_i}(v_l,v_j)+\angle^{\uparrow}_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=
\angle_{v_i}(v_l,v_j')+\angle_{v_j}(v_i',v_l)+\angle_{v_l}(v_j,v_i)
<\angle_{v_i}(v_l,v_j)+\angle_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=\pi$.
Lemma \ref{lem:10} thus follows.

\vspace*{-0.10in}
\section{The Triangle Witness Algorithm}
\label{sec:review}
In this section, we briefly review the triangle witness algorithm in \cite{ref:DisserRe10} that
constructs the visibility graph $G=(V,E)$ of the unknown simple polygon $P$.

The triangle witness algorithm is based on Lemma \ref{lem:10}. The
algorithm has $\lceil n/2\rceil$ iterations. In the $k$-th iteration
($1\leq k\leq \lceil n/2\rceil$),
the algorithm checks, for each $i = 0,1,\ldots, n-1$, whether $v_i$ is
visible to $v_{i+k}$. After all iterations, the edge set
$E$ can be obtained. To this end, the algorithm maintains two maps $F$
and $B$: $F[v_i][v_j]=t$ if $v_j$ is identified as
the $t$-th visible vertex to $v_i$
in the CCW order, i.e., $v_j= vis_t(v_i)$; the definition of $B$ is
the same as $F$. During the algorithm, $F$ will be filled in the CCW
order and $B$ will be filled in the clockwise (CW) order. When the algorithm
finishes, for each $v_i$, $F[v_i]$ will have all visible vertices to $v_i$ on
the chain $ch(v_{i+1},v_{\lceil n/2\rceil})$ while $B[v_i]$ will have
all visible vertices to $v_i$ on the chain $ch(v_{\lceil
n/2\rceil}, v_{i-1})$. Thus, $F[v_i]$ and $B[v_i]$ together contain all visible
vertices of $P$ to $v_i$.
For ease of description, we also treat $F[v_i]$ and
$B[v_i]$ as sets, e.g., $v_l\in F[v_i]$ means that there is an entry
$F[v_i][v_l]$ and $|F[v_i]|$ means the number of entries in the
current $F[v_i]$.

Initially, when $k=1$, since every
vertex is visible to its two neighbors along the boundary of $P$, we have $F[v_i][v_{i+1}]=1$
and $B[v_i][v_{i-1}]=deg(v_i)$ for each $v_i$. In the $k$-th
iteration, we determine for each $v_i$, whether $v_i$ is visible to
$v_{i+k}$. Below, we let $j=i+k$.
Note that $|F[v_i]|+1$ is the index of the first visible
vertex to $v_i$ in the CCW order that is not yet identified;
similarly, $(deg(v_{j})-|B[v_{j}]|)$ is the index of the first
visible vertex to $v_{j}$ in the CW order that is not yet
identified. If $v_i$ is visible to $v_{j}$, then we know that
$v_{j}$ is the $(|F[v_i]|+1)$-th visible vertex to $v_i$ and $v_i$
is the $(deg(v_{j})-|B[v_{j}]|)$-th visible vertex to $v_{j}$,
and thus we set $F[v_i][v_{j}]=|F[v_i]|+1$ and
$B[v_{j}][v_i]=deg(v_{j})-|B[v_{j}]|$. If $v_i$ is not visible to
$v_{j}$, then we do nothing.

It remains to discuss how to determine whether $v_i$ is visible to
$v_{j}$. According to Lemma \ref{lem:10}, we need to determine
whether there exists a triangle witness vertex $v_l$ in the chain
$ch(v_{i+1},v_{j-1})$, i.e., $v_l$ is visible to both $v_i$ and $v_{j}$ and
$\angle^{\uparrow}_{v_i}(v_l,v_j)+\angle^{\uparrow}_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=\pi$.
To this end, the algorithm checks every vertex $v_l$ in
$ch(v_{i+1},v_{j-1})$. For each $v_l$, the algorithm first determines
whether $v_l$ is visible to both
$v_i$ and $v_{j}$, by checking whether there is an entry for $v_l$ in $F[v_i]$
and in $B[v_{j}]$. The algorithm utilizes balanced binary search trees
to represent $F$ and $B$, and thus checking whether there is an entry
for $v_l$ in $F[v_i]$ and in $B[j]$ can be done in $O(\log n)$ time. If $v_l$ is
visible to both $v_i$ and $v_{j}$, then the next step is to determine whether
$\angle^{\uparrow}_{v_i}(v_l,v_j)+\angle^{\uparrow}_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=\pi$.
It is easy to know that $\angle_{v_l}(v_j,v_i)$ is
$\angle_{v_l}(F[v_l][v_{j}],B[v_l][v_i])$, which can be found readily from the input.
To obtain $\angle^{\uparrow}_{v_i}(v_l,v_j)$, we claim that it is the angle
$\angle_{v_i}(F[v_i][v_l],|F[v_i]|+1)$. Indeed, observe that all visible
vertices in the chain $ch(v_{i+1},v_{j-1})$ are in the current
$F[v_i]$. As explained above, $|F[v_i]|+1$ is the index of the first visible
vertex to $v_i$ in the CCW order that has not yet been identified, which is
the first visible vertex to $v_i$ in the chain $ch(v_j,v_i)$, i.e, the
vertex $v_j'$. Thus, $\angle_{v_i}(F[v_i][v_l],|F[v_i]|+1)$ is
$\angle_{v_i}(v_l,v_j')$, which is $\angle^{\uparrow}_{v_i}(v_l,v_j)$.
Similarly, $\angle^{\uparrow}_{v_j}(v_i,v_l)$ is the angle
$\angle_{v_j}(deg(v_j)-|B[v_j]|,B[v_j][v_l])$. Note that both the angles
$\angle_{v_i}(F[v_i][v_l],|F[v_i]|+1)$ and
$\angle_{v_j}(deg(v_j)-|B[v_j]|,B[v_j][v_l])$
are known. Algorithm \ref{algo:10} in the Appendix summarizes the whole
algorithm \cite{ref:DisserRe10}.

To analyze the running time of the above triangle witness algorithm,
note that it has $\lceil n/2\rceil$ iterations. In each iteration, the
algorithm checks whether $v_i$ is visible to $v_{i+k}$ for
each $0\leq i\leq n-1$. For each $v_i$, the algorithm checks every $v_l$
for $i+1\leq l\leq i+k-1$, i.e, in the chain $ch(v_{i+1},v_{i+k-1})$.
For each such $v_l$, the algorithm takes $O(\log n)$ time as it
uses balanced binary search trees to represent the two maps $F$ and $B$.
In summary, the overall running time of the triangle witness algorithm in
\cite{ref:DisserRe10} is $O(n^3\log n)$.

\vspace*{-0.10in}
\section{An Improved Triangle Witness Algorithm}
\label{sec:improve}

In this section, we present an improved solution over the triangle
witness algorithm in \cite{ref:DisserRe10}
sketched in Section \ref{sec:review}. Our improved
algorithm runs in $O(n^2)$ time. Since the input size (e.g., the total
number of visibility angles) is $\Theta(n^2)$ in the worst case, our improved
algorithm is worst-case optimal. Our new algorithm follows the high-level
scheme of the triangle witness algorithm in \cite{ref:DisserRe10}, and thus
we call it the {\em improved triangle witness algorithm}.

As in \cite{ref:DisserRe10}, the new algorithm also has $\lceil n/2\rceil$
iterations, and in each iteration, we determine
whether $v_i$ is visible to $v_{i+k}$ for each $0\leq i\leq n-1$.
For every pair of vertices $v_i$ and $v_{i+k}$, let $j=i+k$. To
determine whether $v_i$
is visible to $v_j$, the triangle witness algorithm \cite{ref:DisserRe10}
checks each vertex $v_l$ in the chain $ch(v_{i+1},v_{j-1})$ to
see whether there exists a triangle witness vertex.
In our new algorithm, instead, we claim that we
need to check only one particular vertex, $vis_{|F[v_i]|}(v_i)$, i.e., the
last visible vertex to $v_i$ in the chain $ch(v_{i+1},v_{j-1})$ in the
CCW order, as stated in the following lemma.

\begin{figure}[t]
\begin{minipage}[t]{\linewidth}
\begin{center}
\includegraphics[totalheight=1.5in]{visible.eps}
\caption{\footnotesize Illustrating Lemma \ref{lem:20}: $v'$ is
$vis_{|F[v_i]|}(v_i)$, the
last visible vertex to $v_i$ in $ch(v_{i+1},v_{j-1})$; $v_i$ is
visible to $v_j$ if and only if $v'$ is a triangle witness vertex.
}\label{fig:visible}
\end{center}
\end{minipage}
\end{figure}

\begin{figure}[t]
\begin{minipage}[t]{\linewidth}
\begin{center}
\includegraphics[totalheight=1.5in]{visPolygon.eps}
\caption{\footnotesize Illustrating the visibility polygon $P(i)$
for the example in Fig.~\ref{fig:visible}: The gray (pink) area is
$P(i)$, which is a star-shaped polygon with the vertex $v_i$ as a kernel point.
}\label{fig:visPolygon}
\end{center}
\end{minipage}
\end{figure}

\begin{figure}[t]
\begin{minipage}[t]{\linewidth}
\begin{center}
\includegraphics[totalheight=1.5in]{boundary.eps}
\caption{\footnotesize Illustrating $P'(i)$ for the example in
Fig.~\ref{fig:visible}: The thick line segments form $P'(i)$.
}\label{fig:boundary}
\end{center}
\end{minipage}
\end{figure}

\vspace*{-0.07in}
\begin{lemma}\label{lem:20}
The vertex $v_i$ is visible to $v_j$ if and only if the vertex
$vis_{|F[v_i]|}(v_i)$ is a triangle witness vertex for $v_i$ and $v_j$.
\end{lemma}
\vspace*{-0.07in}
\begin{proof}
Let $v'$ denote the vertex $vis_{|F[v_i]|}(v_i)$, which is the last visible vertex
to $v_i$ in the chain $ch(v_{i+1},v_{j-1})$ in the CCW order.
Recall that $v'$ being a triangle witness vertex for $v_i$ and $v_j$
is equivalent to saying that $v'$ is visible to both $v_i$ and $v_j$ and
$\angle^{\uparrow}_{v_i}(v',v_j)+\angle^{\uparrow}_{v_j}(v_i,v')+\angle_{v'}(v_j,v_i)=\pi$.

If $v_i$ is visible to $v_j$, then we prove below that $v'$ is a triangle
witness vertex for $v_i$ and $v_j$, i.e., we prove that $v'$ is visible to both $v_i$ and
$v_j$ and
$\angle^{\uparrow}_{v_i}(v',v_j)+\angle^{\uparrow}_{v_j}(v_i,v')+\angle_{v'}(v_j,v_i)=\pi$.
Refer to Fig.~\ref{fig:visible} for an example.
Let $P(v_i)$ denote the subpolygon of $P$ that is visible to
the vertex $v_i$. Usually, $P(v_i)$ is called the {\em visibility
polygon} of $v_i$ and it is well-known that $P(v_i)$ is
a star-shaped polygon with $v_i$ as a kernel point
(e.g., see \cite{ref:AsanoVi00}). Figure~\ref{fig:visPolygon}
illustrates $P(v_i)$.
Since $v'$ is the last visible vertex to $v_i$ in
$ch(v_{i+1},v_{j-1})$ and $v_j$ is visible to $v_i$, we claim that
$v_j$ is also visible to $v'$. Indeed, since both $v'$ and $v_j$ are visible to $v_i$, $v'$
and $v_j$ are both on the boundary of the visibility polygon $P(v_i)$.
Let $P'(v_i)$ denote the portion of the boundary of $P(v_i)$ from $v'$ to
$v_j$ counterclockwise (see Fig.~\ref{fig:boundary}).
We prove below that $P'(v_i)$ does not contain
any vertex of $P$ except $v'$ and $v_j$.
First, $P'(v_i)$ cannot contain any vertex in the chain
$ch(v_{j+1},v_{i-1})$ (otherwise, $v_j$ would not be visible to
$v_i$). Let the index of the vertex $v'$ be $l$, i.e.,
$v'= v_l$. Similarly, $P'(v_i)$ cannot contain any vertex in the chain
$ch(v_{i+1},v_{l-1})$ (otherwise, $v'$ would not be visible to
$v_i$). Finally, $P'(v_i)$ cannot contain any vertex in the chain
$ch(v_{l+1},v_{j-1})$, since otherwise $v'$ would not be the last
visible vertex to $v_i$ in $ch(v_{i+1},v_{j-1})$. Thus, $P'(v_i)$ does
not contain any vertex of $P$ except $v'$ and $v_j$. Therefore, the
region bounded by $P'(v_i)$, the line segment connecting $v_i$ and
$v_j$, and the line segment connecting $v_i$ and $v'$ must be convex (in fact,
it is always a triangle) and this region is entirely contained in $P$.  This
implies that $v_j$ is visible to $v'$.
Hence, the three vertices $v_i,v_j$, and $v'$ are mutually visible to each
other, and we have
$\angle^{\uparrow}_{v_i}(v_l,v_j)+\angle^{\uparrow}_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=
\angle_{v_i}(v_l,v_j)+\angle_{v_j}(v_i,v_l)+\angle_{v_l}(v_j,v_i)=\pi$.

On the other hand, if $v'$ is a triangle witness vertex
for $v_i$ and $v_j$, then by Lemma
\ref{lem:10}, the vertex $v_i$ is visible to $v_j$. The lemma thus
follows.
\end{proof}

By Lemma \ref{lem:20}, to determine whether $v_i$ is visible to
$v_j$, instead of checking every vertex in $ch(v_{i+1},v_{j-1})$, we
need to consider only the vertex $vis_{|F[v_i]|}(v_i)$ in the current set $F[v_i]$.
Hence, Lemma \ref{lem:20} immediately reduces the running time of the triangle
witness algorithm by an $O(n)$ factor. The other $O(\log n)$ factor
improvement is due to a new way of defining and representing the maps $F$ and
$B$, as elaborated below. In the following discussion.
let $v'$ be the vertex $vis_{|F[v_i]|}(v_i)$.

In our new algorithm, to determine whether $v_i$ is visible
to $v_j$, we check whether $v'$ is a triangle witness vertex for $v_i$ and $v_j$.
To this end, we already
know that $v'$ is visible to $v_i$, but we still need to check whether $v'$
is visible to $v_j$. In the previous triangle witness algorithm
\cite{ref:DisserRe10}, this
step is performed in $O(\log n)$ time by representing $F$ and $B$ using
balanced binary search trees. In our new algorithm, we handle this
step in $O(1)$ time, by redefining $F$ and $B$ and using a new way to
represent them.

We redefine $F$ as follows: $F[v_i][v_j]=t$
if $v_j$ is the $t$-th visible vertex to $v_i$ in the CCW order; if
$v_j$ is not visible to $v_i$ or $v_j$ has not yet been identified,
then $F[v_i][v_j]=0$. For convenience, we let
$F[v_i]=F[v_i][v_{i+1},v_{i+2},\ldots,v_{i-1}]$.
Thus, in our new definition, the size of
$F[v_i]$ is fixed throughout the algorithm, i.e., $|F[v_i]|$ is always
$n-1$. In
addition, for each $v_i$, the new algorithm maintains two variables
$L_i$ and $I_i$ for $F[v_i]$, where $L_i$ is the number of non-zero
entries in the current $F[v_i]$, which is also the number of visible
vertices to $v_i$ that have been identified
(i.e., the number of visible vertices to $v_i$
in the chain $ch(v_{i+1},v_{i+k-1})$) up to the $k$-th iteration,
and $I_i$ is the index
of the last non-zero entry in the current $F[v_i]$, i.e., $I_i$ is the
last visible vertex to $v_i$ in the chain $ch(v_{i+1},v_{i+k-1})$ in
the CCW order.
Similarly, we redefine $B$ in the same way as $F$, i.e., for
each $v_i$, $B[v_i]=B[v_i][v_{i+1},v_{i+2},\ldots,v_{i-1}]$ and $B[v_i][v_j]=t$
if $v_j$ is the $t$-th visible vertex to $v_i$ in the CCW order.
Further, for each $v_i$, we also maintain
two variables $L_i'$ and $I_i'$ for $B[v_i]$, where $L_i'$ is the
number of non-zero entries in the current $B[v_i]$, which is also the
number of visible vertices to $v_i$ in the chain
$ch(v_{i-k+1},v_{i-1})$ (up to the $k$-th iteration), and $I_i'$ is the
index of the first non-zero entry in the current $B[v_i]$, i.e., $I_i'$
is the first visible vertex to $v_i$ in the chain
$ch(v_{i-k+1},v_{i-1})$ in the CCW order. During the
algorithm, the array $F[v_i]$ will be filled in the CCW order, i.e.,
from the first entry
$F[v_i][v_{i+1}]$ to the end while the array $B[v_i]$ will be filled
in the CW order, i.e, from the last entry $B[v_i][v_{i-1}]$ to the
beginning. When the algorithm finishes, $F[v_i]$ will
contain all the visible vertices to $v_i$ in the chain
$ch(v_{i+1},v_{i+\lceil n/2 \rceil})$, and thus only the entries of the first half
of $F[v_i]$ are possibly filled with non-zero values.
Similarly, only the entries of the second half of $B[v_i]$ are possibly
filled with non-zero values. Below, we discuss the implementation details of
our new algorithm, which is summarized in Algorithm \ref{algo:20}.

\begin{algorithm}[t]
\caption{The Improved Triangle Witness Algorithm}
\label{algo:20}
\KwIn{$n$, $(v_1,v_2,\ldots,v_n)$, $deg(v_i)$, and the angles
$\angle_{v_i}(\cdot,\cdot)$ for each $0\leq i\leq n-1$.}
\KwOut{The edge set $E$ of the visibility graph $G$ for the target polygon $P$.}
\BlankLine
\tcc{All indices below are understood modulo $n$.}
$E\leftarrow \emptyset$\;
\For{$i\leftarrow 0$ \KwTo $n-1$}{
$F[v_i][v_{i+1},v_{i+2},\ldots,v_{i-1}]\leftarrow 0$\;
$B[v_i][v_{i+1},v_{i+2},\ldots,v_{i-1}]\leftarrow 0$\;
}
\For{$i\leftarrow 0$ \KwTo $n-1$}{
$E\leftarrow E\cup \{e(v_i,v_{i+1})\}$\;
$F[v_i][v_{i+1}]\leftarrow 1$\;
$B[v_i][v_{i-1}]\leftarrow deg(v_{i})$\;
$L_i\leftarrow 1, I_i\leftarrow v_{i+1}, L'_i\leftarrow 1,
I_i'\leftarrow v_{i-1}$\;
}

\For{$k\leftarrow 2$ \KwTo $\lceil n/2 \rceil$}{
\For{$i\leftarrow 0$ \KwTo $n-1$}{
$j\leftarrow i+k$\;
$v'\leftarrow I_i$\;
\If{$B[v_j][v']>0$}{
$\angle^{\uparrow}_{v_i}(v',v_j)\leftarrow \angle_{v_i}(F[v_i][v'],L_i+1)$\;
$\angle^{\uparrow}_{v_j}(v_i,v')\leftarrow \angle_{v_j}(deg(v_j)-L_i',B[v_j][v'])$\;
$\angle_{v'}(v_j,v_i)\leftarrow \angle_{v'}(F[v'][v_j],B[v'][v_i])$\;
}
\If{$\angle^{\uparrow}_{v_i}(v',v_j)+\angle^{\uparrow}_{v_j}(v_i,v')+\angle_{v'}(v_j,v_i)=\pi$}{
$E\leftarrow E\cup \{e(v_i,v_j)\}$\;
$F[v_i][v_j]\leftarrow L_i+1$\;
$B[v_j][v_i]\leftarrow deg(v_j)-L_j'$\;
$L_i\leftarrow L_i+1$, $L'_j\leftarrow L'_j+1$, $I_i\leftarrow v_j$,
$I'_j\leftarrow v_i$\;
}
}
}
\end{algorithm}

Initially, when $k=1$, for each $v_i$, we set $F[v_i][v_{i+1}]=1$ and
$B[v_i][v_{i-1}]=deg(v_i)$, and set all other entries
of $F[v_i]$ and $B[v_i]$ to zero. In addition, we set
$L_i=1$, $I_i=v_{i+1}$ and $L'_i=1$, $I'_i=v_{i-1}$.  In the $k$-th
iteration, with $1<k\leq \lceil n/2 \rceil$, for each $v_i$,
we check whether $v_i$ is visible to $v_j$,
with $j=i+k$. If $v_i$ is not visible to $v_j$, then we do nothing.
Otherwise, we set $F[v_i][v_j]=L_i+1$ and increase $L_i$ by one;
similarly, we set $B[v_j][v_i]=deg(v_j)-L'_j$ and increase $L'_j$ by one.
Further, we set $I_i=v_j$ and $I_j'=v_i$.

It remains to show how to check whether $v_i$ is visible to $v_j$.
By Lemma \ref{lem:20}, we need to determine whether
$v'$ is a triangle witness vertex for $v_i$ and $v_j$. Since $v'$ is the last visible
vertex to $v_i$ in the chain $ch(v_{i+1},v_{j-1})$ in the CCW order,
based on our definition, $v'$ is the vertex $I_i$. After knowing
$v'$, we then check whether $v'$ is visible to $v_j$, which can be
done by checking whether $B[v_j][v']$ is zero, in constant time.
If $B[v_j][v']$ is
zero, then $v'$ is not visible to $v_j$ and $v'$ is not a triangle
witness vertex; otherwise, $v'$ is visible to
$v_j$. (Note that we can also check whether $F[v'][v_j]$ is zero.)
In the following, we assume that $v'$ is visible to $v_j$. The next step is
to determine whether
$\angle^{\uparrow}_{v_i}(v',v_j)+\angle^{\uparrow}_{v_j}(v_i,v')+\angle_{v'}(v_j,v_i)=\pi$.
To this end, we must know the involved three angles. Similar
to the discussion in Section \ref{sec:review}, we have
$\angle_{v'}(v_j,v_i)=\angle_{v'}(F[v'][v_j],B[v'][v_i])$,
$\angle^{\uparrow}_{v_i}(v',v_j)=\angle_{v_i}(F[v_i][v'],L_i+1)$, and
$\angle^{\uparrow}_{v_j}(v_i,v')=\angle_{v_j}(deg(v_j)-L_j',B[v_j][v'])$.
Thus, all these three angles can be
obtained in constant time. Hence, the step of checking whether $v_i$
is visible to $v_j$ can be performed in constant time, which reduces
another $O(\log n)$ factor from the running time of the previous
triangle witness algorithm in \cite{ref:DisserRe10}.
Algorithm \ref{algo:20} summarizes the whole algorithm. Clearly, the running
time of our new algorithm is bounded by $O(n^2)$.

\vspace*{-0.07in}
\begin{theorem}\label{theo:10}
Given the visibility angles and an ordered vertex sequence of a simple
polygon $P$, the improved triangle witness algorithm can reconstruct
$P$ (up to similarity) in $O(n^2)$ time.
\end{theorem}
\vspace*{-0.07in}

As discussed in \cite{ref:DisserRe10}, the above algorithm can also be used
to determine whether the input angle data are consistent. Namely, if
there is no polygon that can fit the input angle data, then
the algorithm in Theorem \ref{theo:10} can be used to report this
case as well.