First and foremost, I thank my advisor, Dr. Claire Cardie, for all of her guidance, patience, and instruction in the ways of the research world. Claire is a truly gifted technical writer, and I continue to strive to live up to her high standards. I would like to particularly thank my committee members, Dr. Jim Bell, Dr. Marie desJardins, and Dr. Bart Selman, for seeing me through this long journey and for offering good advice at critical points along the way. Several others contributed to this work. Sugato Basu generously contributed the graphs in Section 3.6 and several useful email exchanges. Dr. Seth Rogers and Dr. Stefan Schroedl collaborated with me on the road map refinement problem. Dr. Jim Bell worked closely with me on the analysis of STIS Mars observations, supplying the data set, offering advice and encouragement, and interpreting results, despite his hectic schedule. I would also like to thank Jascha Sohl-Dickstein, Jason Soderblom, and Eldar Dobrea for their assistance with the STIS data sets and general good cheer.

My informal advisors and mentors have been invaluable. Dr. Pat Langley has been a reliable collaborator and friend since I asked him for a summer job in the spring of 2000. Dr. Dennis DeCoste was an excellent supervisor at JPL and quite exhilarating to work with. Dr. Elaine Weyuker has been my mentor and frequent email correspondant since 1998 and repeatedly offered me priceless advice. I would also like to thank Dr. Chris Johnson at the University of Utah for being an inspiration and a role model. Even more significantly, I thank my parents, David and Lois, for their lifelong guidance and steadfast support in my pursuit of the Ph.D.

Many of my friends have contributed in significant ways to the completion of this work. Dr. Amy McGovern was my thesis buddy and offered a slew of critical insights on the initial drafts of each chapter. This dissertation would truly suffer in the absence of her input. Although she beat me to the title, she won't beat me to Mars! David Kempe shed brilliant light on the formal analysis of my algorithms and tactfully pointed out my errors. Lengthy discussions with Dan Klein about the nature of constrained clustering made me confront several hard questions and to emerge the better for it. Jeff Vinocur presented me with a very thorough proofreading of a nearly-final draft, and his suggestions helped add the final polish it needed. Andy Sfekas and Dr. Kim Cleland were the best friends I could hope for during my final year. They cheered me on in my job interviews and at my defense and didn't complain (too much) when I couldn't come out to play because I had to write. Westley Weimer, friend and aite, was there from the beginning. His critiques and suggestions added significantly to my research progress and the quality of the implementation. His friendship and sense of humor carried me through several difficult times.

There are several institutions that have contributed financially to the research that produced this dissertation. I would like to thank the National Science Foundation for three years of support as a Graduate Research Fellow. I would also like to thank NSF Grant IRI--9624639 and DARPA TIDES Grant N66001-00-C-8009. I also thank the Jet Propulsion Laboratory and DaimlerChrysler's Research and Technology Center for exceedingly productive summer internships.

Finally, I would like to thank astra, stardust, schneller, zinger, and the CFS linux cluster for their tireless dedication to helping me develop code and to running my clustering experiments. In addition, many thanks go to nova, astra's faithful printer sidekick.