# David G. Kirkpatrick

> Canadian computer scientist (1953-)

**Wikidata**: [Q92724](https://www.wikidata.org/wiki/Q92724)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/David_G._Kirkpatrick)  
**Source**: https://4ort.xyz/entity/david-g-kirkpatrick

## Summary
David G. Kirkpatrick is a Canadian computer scientist born in 1953 who is best known for co-developing the Kirkpatrick–Seidel algorithm for computing convex hulls efficiently. He is a professor at the University of British Columbia and a Fellow of the Royal Society of Canada, recognized for his significant contributions to computational geometry and algorithms research.

## Biography
- Born: 1953
- Nationality: Canada
- Education: University of Toronto (as educated institution)
- Known for: Kirkpatrick–Seidel algorithm
- Employer(s): University of British Columbia
- Field(s): Computer science, computational geometry, algorithms

## Contributions
David G. Kirkpatrick's most significant contribution to computer science is the Kirkpatrick–Seidel algorithm, which he developed with Michael Seidel. This algorithm computes the convex hull of a set of points in the plane with optimal time complexity of O(n log h), where n is the number of input points and h is the number of points in the hull. This breakthrough represented a major advancement in computational geometry, providing a more efficient solution than previous methods when the number of hull points is much smaller than the total number of input points. Beyond this landmark algorithm, Kirkpatrick has made substantial contributions to geometric algorithms, graph theory, and discrete mathematics through his extensive research and supervision of graduate students. His work has influenced the development of efficient algorithms for spatial data processing, computer graphics, and various applications requiring geometric computations. As a professor at the University of British Columbia, he has mentored numerous doctoral students who have gone on to make their own contributions to computer science, including notable researchers like Bettina Speckmann, Teresa M. Przytycka, and other prominent figures in the field.

## FAQs
### Q: What is the Kirkpatrick–Seidel algorithm?
A: The Kirkpatrick–Seidel algorithm is a method for computing the convex hull of a set of points in the plane with optimal time complexity of O(n log h), where n is the number of input points and h is the number of points in the hull. It represents a significant improvement over previous convex hull algorithms.

### Q: Where does David G. Kirkpatrick work?
A: David G. Kirkpatrick is affiliated with the University of British Columbia, where he serves as a professor in the computer science department.

### Q: What recognition has David G. Kirkpatrick received?
A: David G. Kirkpatrick is a Fellow of the Royal Society of Canada, one of the country's highest honors for distinguished scholarship and research excellence.

## Why They Matter
David G. Kirkpatrick's impact on computer science extends far beyond his most famous algorithm. The Kirkpatrick–Seidel algorithm fundamentally changed how computational geometers approach convex hull problems, introducing techniques that have influenced subsequent research in geometric algorithms. His work established new theoretical foundations for understanding the complexity of geometric problems and demonstrated how problem-specific optimizations could lead to more efficient solutions. Through his role as a doctoral advisor and educator at the University of British Columbia, Kirkpatrick has shaped the careers of numerous researchers who continue to advance the field. His academic lineage includes prominent computer scientists who have carried forward his innovations in computational geometry, algorithms, and discrete mathematics. The practical applications of his work span multiple domains including computer graphics, geographic information systems, robotics, and pattern recognition, where efficient geometric computations are essential. His recognition as a Fellow of the Royal Society of Canada underscores his lasting contribution to Canadian and international scientific excellence in computer science.

## Notable For
• Co-developing the Kirkpatrick–Seidel algorithm for convex hull computation with optimal O(n log h) time complexity
• Being elected as a Fellow of the Royal Society of Canada for distinguished contributions to computer science
• Mentoring influential researchers including Bettina Speckmann, Teresa M. Przytycka, and other prominent computer scientists
• Academic affiliation with the University of British Columbia as a leading figure in computational geometry
• Doctoral student under Allan Borodin, continuing a distinguished lineage in theoretical computer science

## Body
### Academic Career
David G. Kirkpatrick pursued his education at the University of Toronto before embarking on an academic career focused on computer science and computational geometry. He completed his doctorate under the supervision of Allan Borodin, establishing him within a prestigious academic lineage in theoretical computer science.

### Research Focus
Kirkpatrick's primary research area centers on computational geometry and algorithm design. His work addresses fundamental problems in geometric computation, with particular emphasis on developing efficient algorithms for spatial data processing and geometric optimization problems.

### Algorithmic Innovation
The Kirkpatrick–Seidel algorithm represents his most celebrated contribution to computer science. This algorithm solves the planar convex hull problem with time complexity O(n log h), where n is the number of input points and h is the number of points on the convex hull. This represents an improvement over previous algorithms when h is significantly smaller than n.

### Academic Leadership
As a faculty member at the University of British Columbia, Kirkpatrick has supervised numerous doctoral students who have become prominent researchers in their own right. His doctoral students include Bettina Speckmann, Teresa M. Przytycka, Lisa Higham, and others who have made significant contributions to computer science.

### Professional Recognition
Kirkpatrick's election as a Fellow of the Royal Society of Canada represents one of Canada's highest academic honors, recognizing his distinguished contributions to computer science research and his impact on the field of computational geometry.

## Schema Markup
```json
{
  "@context": "https://schema.org",
  "@type": "Person",
  "name": "David G. Kirkpatrick",
  "jobTitle": "Computer Scientist, Professor",
  "worksFor": {"@type": "Organization", "name": "University of British Columbia"},
  "nationality": {"@type": "Country", "name": "Canada"},
  "birthDate": "1953",
  "alumniOf": [{"@type": "EducationalOrganization", "name": "University of Toronto"}],
  "knowsAbout": ["Computer Science", "Computational Geometry", "Algorithms"],
  "sameAs": ["https://www.wikidata.org/wiki/Q912927", "https://en.wikipedia.org/wiki/David_G._Kirkpatrick"],
  "description": "Canadian computer scientist known for the Kirkpatrick–Seidel algorithm and contributions to computational geometry"
}

## References

1. Mathematics Genealogy Project