Fast Algorithms Using Minimal Data Structures for Common Topological Relationships in Large, Irregularly-spaced Topographic Data Sets

Digital terrain models (DTM) typically contain large numbers of postings, from hundreds of thousands to billions. Many algorithms that run on DTMs require topological knowledge of the postings, such as finding nearest neighbors, finding the posting closest to a chosen location, etc. If the postings are arranged irregu- larly, topological information is costly to compute and to store. This paper offers a practical approach to organizing and searching irregularly-space data sets by presenting a collection of efficient algorithms (O(N),O(lgN)) that compute important topological relationships with only a simple supporting data structure. These relationships include finding the postings within a window, locating the posting nearest a point of interest, finding the neighborhood of postings nearest a point of interest, and ordering the neighborhood counter-clockwise. These algorithms depend only on two sorted arrays of two-element tuples, holding a planimetric coordinate and an integer identification number indicating which posting the coordinate belongs to. There is one array for each planimetric coordinate (eastings and northings). These two arrays cost minimal overhead to create and store but permit the data to remain arranged irregularly.

Asset Pricing with Heterogeneous Agents, Incomplete Markets and Trading Constraints

The consumption capital asset pricing model is the standard economic model used to capture stock market behavior. However, empirical tests have pointed out to its inability to account quantitatively for the high average rate of return and volatility of stocks over time for plausible parameter values. Recent research has suggested that the consumption of stockholders is more strongly correlated with the performance of the stock market than the consumption of non-stockholders. We model two types of agents, non-stockholders with standard preferences and stock holders with preferences that incorporate elements of the prospect theory developed by Kahneman and Tversky (1979). In addition to consumption, stockholders consider fluctuations in their financial wealth explicitly when making decisions. Data from the Panel Study of Income Dynamics are used to calibrate the labor income processes of the two types of agents. Each agent faces idiosyncratic shocks to his labor income as well as aggregate shocks to the per-share dividend but markets are incomplete and agents cannot hedge consumption risks completely. In addition, consumers face both borrowing and short-sale constraints. Our results show that in equilibrium, agents hold different portfolios. Our model is able to generate a time-varying risk premium of about 5.5% while maintaining a low risk free rate, thus suggesting a plausible explanation for the equity premium puzzle reported by Mehra and Prescott (1985).