David Eppstein - Böcker

This book surveys the mathematical and computational properties of finite sets of points in the plane, covering recent breakthroughs on important problems in discrete geometry, and listing many open problems. It unifies these mathematical and computational views using forbidden configurations, which are patterns that cannot appear in sets with a given property, and explores the implications of this unified view. Written with minimal prerequisites and featuring plenty of figures, this engaging book will be of interest to undergraduate students and researchers in mathematics and computer science. Most topics are introduced with a related puzzle or brain-teaser. The topics range from abstract issues of collinearity, convexity, and general position to more applied areas including robust statistical estimation and network visualization, with connections to related areas of mathematics including number theory, graph theory, and the theory of permutation patterns. Pseudocode is included for many algorithms that compute properties of point sets.

This book surveys the mathematical and computational properties of finite sets of points in the plane, covering recent breakthroughs on important problems in discrete geometry, and listing many open problems. It unifies these mathematical and computational views using forbidden configurations, which are patterns that cannot appear in sets with a given property, and explores the implications of this unified view. Written with minimal prerequisites and featuring plenty of figures, this engaging book will be of interest to undergraduate students and researchers in mathematics and computer science. Most topics are introduced with a related puzzle or brain-teaser. The topics range from abstract issues of collinearity, convexity, and general position to more applied areas including robust statistical estimation and network visualization, with connections to related areas of mathematics including number theory, graph theory, and the theory of permutation patterns. Pseudocode is included for many algorithms that compute properties of point sets.

The focus of this book is a mathematical structure modeling a physical or biological system that can be in any of a number of ‘states. ’ Each state is characterized by a set of binary features, and di?ers from some other nei- bor state or states by just one of those features. In some situations, what distinguishes a state S from a neighbor state T is that S has a particular f- ture that T does not have. A familiar example is a partial solution of a jigsaw puzzle, with adjoining pieces. Such a state can be transformed into another state, that is, another partial solution or the ?nal solution, just by adding a single adjoining piece. This is the ?rst example discussed in Chapter 1. In other situations, the di?erence between a state S and a neighbor state T may reside in their location in a space, as in our second example, in which in which S and T are regions located on di?erent sides of some common border. We formalize the mathematical structure as a semigroup of ‘messages’ transforming states into other states. Each of these messages is produced by the concatenation of elementary transformations called ‘tokens (of infor- tion). ’ The structure is speci?ed by two constraining axioms. One states that any state can be produced from any other state by an appropriate kind of message. The other axiom guarantees that such a production of states from other states satis?es a consistency requirement.

The focus of this book is a mathematical structure modeling a physical or biological system that can be in any of a number of ‘states. ’ Each state is characterized by a set of binary features, and di?ers from some other nei- bor state or states by just one of those features. In some situations, what distinguishes a state S from a neighbor state T is that S has a particular f- ture that T does not have. A familiar example is a partial solution of a jigsaw puzzle, with adjoining pieces. Such a state can be transformed into another state, that is, another partial solution or the ?nal solution, just by adding a single adjoining piece. This is the ?rst example discussed in Chapter 1. In other situations, the di?erence between a state S and a neighbor state T may reside in their location in a space, as in our second example, in which in which S and T are regions located on di?erent sides of some common border. We formalize the mathematical structure as a semigroup of ‘messages’ transforming states into other states. Each of these messages is produced by the concatenation of elementary transformations called ‘tokens (of infor- tion). ’ The structure is speci?ed by two constraining axioms. One states that any state can be produced from any other state by an appropriate kind of message. The other axiom guarantees that such a production of states from other states satis?es a consistency requirement.

The 17th International Symposium on Graph Drawing (GD 2009) was held in Chicago, USA, September 22-25, 2009, and was attended by 91 participants from 19 countries. In response to the call for papers, the Program Committee received 79 s- missions. Each submission was reviewed by at least three Program Committee members. Following substantial discussions, the committee accepted 31 long - pers and 4 short papers. All authors received detailed reviewers' comments. In a separate submission process, 10 posters were accepted. These were described during the conference,and displayedatthe conferencesite. Eachposter was also granted a two-page description in the conference proceedings. Two invited speakers, J' anos Pach from EPFL Lausanne and R' eny Institute, and Martin Wattenberg from IBM Research, gave absorbing talks during the conference. Prof. Pach looked at the class of string graphs, and tantalized us to consider why their properties are so mathematically beautiful. Dr. Watt- berg showed how sometimes twisting the standard rules of graph drawing can illuminate unexpected information contained in graphs.Keepingwithtradition,the symposiumhostedthe 15thAnnualGraphDr- ingContest,including aGraphDrawingChallengeforconferenceattendees.The contest elicited robust participation from the community with 27 submissions. These proceedings end with a detailed report of the contest. As always, the success of a conference such as this relies on the help of many people. Our thanks to the Program Committee and all of the external referees who worked so hard to sift for the best among the submitted papers. The OrganizingCommittee providedus with admirablefacilities,a ?ne banquet, andtookcareofsomanyotherdetailsthatitwashardtobelievetherewereonly threemembers:Jennifer McClelland,MichaelJ.PelsmajerandMarcusSchaefer.

The book describes up-to-date applications and relevant theoretical results. These applications come from various places, but the most important one, numerically speaking, is the internet based educational system ALEKS. The ALEKS system is bilingual English-Spanish and covers all of mathematics, from third grade to the end of high school, and chemistry. It is also widely used in higher education because US students are often poorly prepared when they reach the university level. The chapter by Taagepera and Arasasingham deals with the application of knowledge spaces, independent of ALEKS, to the teaching of college chemistry. The four chapters by Albert and his collaborators strive to give cognitive interpretations to the combinatoric structures obtained and used by the ALEKS system. The contribution by Eppstein is technical and develops means of searching the knowledge structure efficiently.