High dose rate (HDR) brachytherapy is a radiation therapy for cancer in the prostate, cervix, breast, head, and neck, including other sites. In HDR brachytherapy, hollow needles are inserted or placed near the cancer site. Radiation is delivered to the patient by a radioactive source which is sequentially threaded through the needles. The dose distribution is controlled by altering the dwell times, the time spent at pre-defined positions on the needles.

HDR brachytherapy has a 90\% cancer-free survival rate at 12 years when used for the treatment of prostate cancer, the focus of this dissertation. However, it can have serious negative side effects such as impotence and incontinence, which are caused by excess radiation exposure and needle puncture of healthy organs near the prostate, or organs at risk (OAR). A major goal of the field is to reduce side effects of HDR brachytherapy without compromising its therapeutic effectiveness. Towards this goal, this dissertation seeks to use mathematical optimization techniques to compute radiation dose distributions which meet clinical objectives and needle configurations which induce less trauma in the patient. We develop planning tools that directly optimize the dose distributions towards the RTOG-0321 standard dose objectives set by the Radiation Therapy Oncology Group and needle configurations which avoid puncturing OAR and use fewer needles than common practice. Specifically, this dissertation makes the following contributions.

Contributions:

1. We developed Inverse Planning by Integer Program (IPIP), the first integer program which directly optimizes dosimetric indices, the standard metrics used to evaluate HDR brachytherapy dose distributions. However, we showed that for anatomy data taken from patients previously treated at the UCSF clinic and the RTOG-0321 dose objectives, CPLEX could not solve IPIP within 30 minutes of computing time using its default parameters.

2. We developed a heuristic algorithm, IPIP-H, which uses two linear programs to compute feasible solutions for IPIP. Thus, it is a polynomial-time heuristic algorithm for IPIP. We used IPIP-H to compute dose plans for the same patients as IPIP. We showed that IPIP-H could compute a dose plan for each patient which met all the dose objectives specified by the RTOG-0321 protocol in less than 30 seconds of computing time (avg. 13 seconds). The solutions computed from IPIP-H were always feasible for IPIP and were within 5% of the optimal solution. We compared IPIP-H to Inverse Planning Simulated Annealing (IPSA), a dose planning model which is clinically deployed and has been used worldwide for over a decade. IPSA was not able to compute a dose plan which met all the dose objectives for any of the patients in our data set using its standard class solution. Therefore, IPSA would require iterations of manual fine tuning of its optimization parameters until a feasible dose plan was found. IPIP-H would not require iteration.

3. We formulated the problem of positioning HDR brachytherapy needles as a spatial coverage problem: given a large candidate set of needles for insertion, anatomy data, and a user parameter, delta, find the smallest candidate needle subset such that the minimum distance between any point in the prostate and a needle in the chosen set is less than delta. We showed that this problem could be represented as a set cover integer program.

4. We developed Needle Planning by Integer Program (NPIP), an algorithm which generates a set of candidate needles represented by skew-line segments, solves an integer program which chooses a candidate needle subset that covers the prostate according to the user-parameter, delta, and verifies that the final needle configuration meets dose objectives by computing a dose plan for it using IPIP. NPIP uses a candidate needle set which is approximately 10 times larger than considered with Hyrbid Inverse Planning Optimization (HIPO), the only other fully computerized needle planning system for HDR brachytherapy known to us. By construction, NPIP avoids choosing needles which penetrate OAR and needles which collide with each other. We used NPIP to compute needle configurations for patients previously treated at the UCSF clinic and compared the computed needle configurations to those implanted by the physician. NPIP could find needle configurations which met the RTOG-0321 dose objectives and used 10 or fewer needles; the physician used 16 needles. NPIP always computed a needle configuration that avoided puncturing the penile bulb; the average number of punctures made by the physician was 5. NPIP required an average of 5 minutes of computing time, but there was a wide range of run times, up to almost one hour. We also conducted a sensitivity analysis of NPIP-generated needle configurations to placement errors on the order expected from current needle insertion robots, which was about 2 mm. We showed that, although dose objectives could be met with 10 or fewer needles, 16 needles were required to meet dose objectives robustly.

5. We designed and implemented the first end-to-end robotic HDR brachytherapy experiment. Our experiment utilized Contributions 1 through 4, and Acubot-RND, a needle insertion robot specialized for needle insertion. We planned and executed NPIP-generated needle configurations in a fully equipped brachytherapy environment on two anatomically-correct gelatin phantoms. There were non-trivial placement errors between the planned needle configuration and the implanted needle configuration. We separated the error into systematic error and random error. We computed the systematic error as the rigid least squares fit between points regularly sampled along the needles in the planned and actual needle configuration. The total RMS error between the planned and actual needle configuration was 3 mm for the first phantom and 5 mm for the second phantom. We computed the random error as the total RMS error between the planned and actual needle configuration after the systematic error was removed. The random error was 1.4 mm for the first phantom and 2.5 mm for the second phantom. Our random errors were close to the placement error of current needle insertion robots which have a more sophisticated calibration device. Although there were discrepancies between the planned and actual needle configuration, we showed that our end-to-end robotic experiment could execute the planned needle configurations with sufficient accuracy to meet the RTOG-0321 dose objectives and avoid puncturing OAR. We compared the needle configurations executed by our robotic workflow with a needle configuration executed by a world-class brachytherapist, who also used 16 needles, met dose objectives and avoided puncturing OAR. Therefore, the needle configurations executed in our experiment are comparable to an expert physician.

In summary, this dissertation has developed mathematical methods which improve the planning of HDR brachytherapy dose distributions and needle configurations. Dose distributions can be directly optimized towards the standard RTOG-0321 dosimetric protocol, or other dose objectives based on constraining dosimetric indices, and needle configurations can be computed which meet dose objectives, use fewer needles than standard practice, and avoid puncturing OAR. We have demonstrated the feasibility of using IPIP and NPIP in a clinical environment using a robotic clinical workflow. These planning methods are a significant step towards reducing side effect of brachytherapy. We leave a clinical translation of these tools to determine if, and the extent, side effects are actually reduced.

This dissertation explores the use of geometric and graphical models for a variety of information search and filtering applications. These models serve to provide an intuitive understanding of the problem domains and as well as computational efficiencies to our solution approaches.

We begin by considering a search and rescue scenario where both human and automated agents share control over a fleet of unmanned aerial vehicles (UAVs) with the goal of locating a missing subject as quickly as possible. We describe a new interface and search framework, Hydra, which merges the intuition, reasoning, and vision capabilities of humans with the computational power of machines to reduce the expected time to locate the subject. The interface allows participating human agents to collaboratively decide where to send the UAVs via spatial dynamic voting, a geometric method for aggregating regional selections (votes) on a map. Via extensive simulation and theoretical analysis, we show that our method can be an effective component of search and rescue operations.

In the next chapter, we present a new graph-theoretical model for filtering a large set of genes to identify those that exhibit the most significant change in expression values between a series of control and test experiments; this is known as the Gene Selection Problem. Although not a geometric model in the traditional sense, graph theory allows us to organize data in abstract geometric spaces, where similarity metrics are used to define relative distances between nodes of data as opposed to working with an absolute coordinate system. Our algorithm first pre-processes the data using statistical hypothesis testing to filter out statistically irrelevant genes, and then we analyze the expression levels recorded for each gene by modeling them on a graph and evaluating the capacity of the cut between the test and control experiments. The capacity of a cut on a graph is a measure of the separation between two disjoint sets of nodes, and we use this value to rank the genes. We evaluated our model on a rich data set assessing the success of embryo implantation in mice in the presence or absence of uterine dendritic cells. A thorough biological analysis of our results enabled the discovery of significant factors that were not identified by more traditional, statistical methods.

In the remaining chapters of this dissertation, we transition to a series of algorithms and models for filtering information in a collaborative, social context. We begin by presenting a new, constant-time recommender system for jokes that adapts in real-time to changes in user preferences or mood. We also present an extension of this system that makes personalized recommendations on where participants might wish to donate their money.

Chapters 5 and 6 consider the domain of collaborative opinion and idea sharing in an online setting. We present a new tool, Opinion Space, that we are developing for visualizing and crowdsourcing a diversity of insights collected via textual responses to a discussion question. Opinion Space projects participants onto a two-dimensional plane using Principal Component Analysis based on their levels of agreement with a series of statements. The projection is specifically designed so that participants with similar opinions will be near each other in the space; this allows participants to easily navigate the diversity of opinions shared by others.

Over the last two years, we have released multiple versions of Opinion Space and collected several rich data sets for analysis. In Chapter 5 we describe the interface and design decisions made when building the site. We also present results from a controlled user study comparing user engagement with Opinion Space versus more traditional models of online opinion sharing (specifically, linear comment lists). Not only did we find that participants were significantly more engaged with Opinion Space, but they had significantly higher levels of agreement with and respect for the responses that they read.

In Chapter 6 we present several models, both geometric and statistical, for ranking the contributions of our participants based on how insightful they are. Our primary model considers the spatial relationships between users in addition to the ratings they give each other; the intuition behind the model can be described as follows. By giving users the opportunity to rate the responses they read, we allow for the very likely possibility that users will only promote their own interests and rate opposing opinions poorly, even if it is a well-written and pointed response. We claim that this behavior is of little value towards our objective of identifying insightful ideas, because users are simply reinforcing their own opinions. Visually, one can imagine that the space of users is partitioned into subgroups or smaller spheres of agreement, and we are interested in emphasizing the comments where these spheres intersect. In this scenario, we have identified users of different viewpoints that have potentially found a legitimate middle ground.

Chapter 7 provides concluding remarks on our work with Opinion Space from a New Media and social responsibility perspective, and we present preliminary results on future work in the area.