Office
529 Soda Hall
Computer Science Division
University of California at Berkeley
Berkeley, California 94720-1776
(510) 642-3936 [five ten NICE ZEN]
Office hours
By appointment only (until Spring 2026).
Email is the best way to contact me.
There's a chance you'll find me in my office afternoons or early evenings
(typically 1–6 PM)
on Mondays, Wednesdays, or Fridays during spring semesters.
While you're by, ask me to make a pot of tea.
I get teas from Upton Tea Imports,
a first-rate importer in Massachusetts,
and I enjoy introducing people to the good stuff.
Mornings I sleep.
During summers and fall semesters, I mostly work at home.
Attempts to phone me then are futile.
TRIANGLE.
A production-quality C program for
two-dimensional constrained Delaunay triangulation and quality mesh generation.
See the
Triangle page
to obtain the source code and for hypertext instructions.
I expect to release its three-dimensional successor, Star,
in the near future.
The algorithms behind Triangle and Star are discussed in my dissertation
and in several other papers on my
Papers
page.
STELLAR.
A C program for aggressively improving the quality of tetrahedral meshes,
making them suitable for finite element analysis.
Stellar routinely improves meshes so that the smallest dihedral angle is larger
than 30 degrees and the largest dihedral angle is smaller than 140 degrees.
See the
Stellar page
to obtain the source code, hypertext instructions, and
publications describing its algorithms.
EXACT ARITHMETIC AND ROBUST
GEOMETRIC PREDICATES.
I've written a set of fast routines for exact floating-point
addition and multiplication, which I've used to create
fast correct geometric predicates, namely the two- and three-dimensional
orientation and incircle tests.
These predicates are used to make the Delaunay triangulation routines
in Triangle and Star robust against roundoff error.
See my
Robust Predicates page for more information, for papers,
or to obtain the C source code.
RESEARCH OVERVIEW.
Here's a self-contained summary of some of my research.
This is the fastest way to learn a bit about my work.
THREE SINS OF AUTHORS IN
COMPUTER SCIENCE AND MATH.
A short crotchety essay that will improve your technical writing,
or annoy you trying.
You won't find these sins decried in the usual books of writing advice.
While you're at it, you might be interested in my (less snarky) advice on
Giving an Academic
Talk.
CS 274: COMPUTATIONAL GEOMETRY(Spring 2019,
Spring 2017,
Spring 2015,
Spring 2013,
Autumn 2009,
Autumn 2006,
Spring 2005,
Spring 2003).
Geometric algorithms, analyses, and applications.
Polygons, polytopes, triangulations, planar and spatial subdivisions,
convex hulls, halfspace intersections, Voronoi diagrams,
Delaunay triangulations, arrangements of lines and hyperplanes.
Geometric queries (databases, point location), binary space partitions,
robot motion planning, cartography, solid modeling,
small-dimensional linear programming, and more.
MARTIN ISENBURG, 1972–2021,
In Memoriam.
Martin was a Post-Doctoral Scholar under my supervision
from the summer of 2005 to the summer of 2007.
He developed a software suite called
the LAStools
for fast streaming computation of geographical information (including
Delaunay triangulations) on huge data sets,
which he subsequently promoted through his personal company,
rapidlasso GmbH.
I wrote an extended obituary for him after
his sad early death.
RAVIKRISHNA KOLLURI
in December 2005 completed his Ph.D. on surface reconstruction algorithms,
including
spectral
surface reconstruction, scan registration,
moving least squares interpolation for generating implicit surfaces
(which won the Best Student Paper Award
at the 2005 Symposium on Discrete Algorithms),
and the very cool
power
crust.
Read his dissertation,
From
Range Images to 3D Models.
He now works at Google.
DR. MALCOLM KENDRICK'S
INFORMATIVE AND HILARIOUS 2021 BOOK
The Clot Thickens
is a fascinating review of the biology of atherosclerosis and heart disease.
But I most want to share not the part of his book about
the etiology of heart disease, but rather the part discussing
which lifestyle changes have the greatest effect on lifespan,
based on our present knowledge.
Dr. Kendrick writes, “Despite the fact that it is very rarely done,
it is possible to convert a percentage risk into the common currency of
life expectancy.”
You would think that researchers would do this more often, and
doctors would inform their patients of how many expected months
this or that pill or surgery will add to your life.
But Dr. Kendrick says, “I don't think I have ever seen
anyone else do this, or even attempt to do this?
Possibly because it is just so damned tricky. …
“Doctor:
‘Oh my God you have a 10.3% risk of a cardiovascular event.’
“Patient:
‘Which means… what? Tell me please doctor. Tell me.
I must know.’
“Doctor:
‘It means you have a 10.3% risk of a cardiovascular event—so
you must take a statin every day for the rest of your life.
Here is your prescription. Next!’ ”
Dr. Kendrick's estimates of how much the interventions discussed below extend
lifespan on average involve some guesswork
(and depend on the age at which the intervention is begun), but
we can be reasonably confident that these interventions have
significant positive health effects for the average person.
Observe that this list has little in common with what
most people would expect to be on the list—overrated interventions like
statin drugs, eating less saturated fat, and losing weight.
Dr. Kendrick estimates you might gain
“Three days extra for every five years taking the statin.”
Here are some of his more optimistic estimates.
Potassium might be the most effective supplement you can take;
he suggests it can increase expected lifespan by approximately 5 years.
According to the
Scottish Heart Health study (quoting Dr. Kendrick),
“Men consuming an average of 5,400 mg of potassium per day vs. 1,840 mg
were 55% less likely to die during 7.6 year study
(the highest one-fifth of men vs the lowest one-fifth of men)” and
“Women consuming an average of 4,500 mg of potassium per day vs. 1,560 mg
were 59% less likely to die during 7.6 year study
(the highest one-fifth of women vs the lowest one-fifth of women)”.
Other studies have confirmed similar effects.
Potassium lowers
blood pressure
(“as good, if not better, than any antihypertensive drug” per
Dr. Kendrick) and the risks of arrhythmias, cardiovascular disease,
both hemorrhagic and ischemic strokes
(by factors of 3 and 2,
respectively),
heart attacks, cancer, and death.
For more details, see
this
post by Dr. Kendrick.
He adds, “the most important thing about potassium is that
I cannot find any study, anywhere, which suggests that increasing
potassium consumption may be harmful.
In short, it seems to be something that does only good.”
Be forewarned that it is difficult to get enough potassium from pills
(which are limited to 99 mg in the USA);
daily doses of 3–5 grams are needed.
Buy powder in bulk.
To get 4 grams of elemental potassium, you need about
10.5 grams of potassium citrate, 7.64 grams of potassium chloride,
5.1 grams of potassium bicarbonate, or 24 grams of potassium gluconate.
Note that
chloride
also seems to reduce mortality.
Supplementation with Vitamins B6 (pyridoxine, 20 mg/day),
B9 (folate, 0.8 mg/day—folic acid is not recommended by me;
find real folate), and B12 (0.5 mg/day)
reduces
serum homocysteine, and
homocysteine is
causative of epithelial damage and coronary artery disease and
perhaps also Alzheimer's disease.
Dr. Kendrick estimates that high serum homocysteine may reduce lifespan
by up to 10 years, but
I do not think it has been directly established that the B Vitamins
extend lifespan that much in people with high homocysteine, so
take this entry with a grain of salt (preferably KCl).
Nevertheless, you should be asking your doctor to check your homocysteine levels
at your annual checkup.
Perhaps this is the most surprising entry.
More research needs to be done, but sildenafil (Viagra) appears to have
a strong effect on mortality, especially from cardiovascular disease.
It produces a lot of nitric oxide and dilates blood vessels, which may explain
its heart-protective effect.
A small, 7.5-year
observational study in Cheshire, UK studied
men with diabetes and a previous heart attack (a very high-risk group).
The group taking sildenafil had a 38% lower risk of heart attack, and
overall mortality was 25.7% in the Viagra group and 40.1% in the control group.
Dr. Kendrick estimates that for high-risk men like those in the study,
long-term use of sildenafil may increase average lifespan by
up to 10 years.
(Caveat: as this figure is for diabetics with a previous heart attack,
it cannot be directly compared with the other figures in this essay.)
Avoid type 2 diabetes and persistent high blood sugars.
Unfortunately, there's controversy about what interventions best treat them.
(Interestingly, diabetes has been treated successfully with both
low-carbohydrate and ultra-low-fat diets, which are
therapeutic for different reasons.)
Type 2 diabetes can reduce expected lifespan by up to an average of
10–20 years.
Avoid air pollution.
Small particulate matter in the air can reduce expected lifespan by
up to an average of 4 years.
People know you shouldn't smoke but are rarely aware of
the magnitude of the harm done by air pollution.
Avoid proton pump inhibitors (PPIs),
a class of drugs that reduce stomach acid.
PPIs reduce expected lifespan by up to an average of 2 years.
Doctors have gone mad prescribing PPIs for
gastroesophageal reflux disease (GERD) and ulcers, but
they're a terrible solution.
They shorten your life
primarily by
increasing cardiovascular mortality.
They're also habit-forming and very difficult to quit.
(Ironically, the best alternative solution for some people is to
increase your stomach acid by taking pills of
betaine HCl,
possibly also with pepsin and/or gentian bitters.
Alternatively, Dr. Michael Eades found in his practice that
a
low-carbohydrate diet usually eliminates GERD.)
Periodontal disease can reduce expected lifespan by 18 months.
The to-do list should probably include magnesium supplementation, and
the don't-do list should surely include corticosteroids, but
I don't have mortality estimates for those.
The don't-do list should also include polypharmacy:
the average American over 80 takes 22 medications regularly, and
a trial that
carefully discontinued some medications in geriatric nursing departments
reduced the one-year mortality from 45% to 21%.
Another result from the Scottish Heart Health study is particularly noteworthy.
Among blood markers,
the most predictive of mortality was excess serum fibrinogen.
Fibrinogen is a clotting factor, and too much of it seems to increase
the rate of strokes and cardiovascular disease.
Unfortunately, we don't know much about how to reduce serum fibrinogen.
Contrary to what you might expect, there was not a clear relationship between
cholesterol and mortality.
High total cholesterol and low HDL cholesterol appear to be predictive of
death by cardiovascular heart disease, but
deaths by other causes are reduced enough to compensate!
“[Wisdom] is earned through disgrace, through painful realization of
the inadequacy of your personal world view.”
—
Nat Hillard
“In my psychedelic, hazy-vision state, where I reach the ultimate
heightened awareness of the beer-buzz, I realise the true meaning of exams:
that professors are evil, torture-loving beings, and that we cannot blame them
for their shortcomings.”
—
Rob Chung
“We need a more lasting form of negative feedback than just
paper rejections.”
— Jonathan Hardwick
Jonathan Shewchuk
The conjugate gradient method
