幾何的な対象を計算機で扱えるよう体系化した学問。コンピュータ・ジオメトリ。 重要な成果に凸包、ボロノイ図、ドローネ図を作るアルゴリズムが挙げられる。
Edelsbrunner は計算幾何学の研究者なので、この本のタイトルはずっと computational geometry だと思っていました（そのタイトルの別著者本は別にあります）。計算幾何学もふつうに漢字変換すると計算機科学になってしまうし耳で聞くとどっちか区別がつかないです。まあそれはどうでもいい話ですが。 卒論で杉原厚吉先生から計算幾何学について多少勉強した程度ですが、パズルのようにアルゴリズムを考える人には向いている学問だと思います。卒論の時は、グラフ構造で立体を記述する方式で、グラフの枝の長さでやられていたところを、枝と枝の角度を入れたときに構造が（局所的に）一意に定まるための条…
2023/10/17のABC323にて入黄したので、いろいろ書きます。 自己紹介とこれまで そういえばしっかりしてなかったので。 私は中学2年生です*1。私の学校は私しか競プロ勢がいないので、競プロ強豪校ではありません。筑駒でも開成でも灘でもないです。*2 数学が得意教科ではありますが、競プロ的な数学の知識は競プロを始めてから身に着けたので、普通の人という解釈でもほぼ問題ないかと思います。算数オリンピックのファイナル進出経験はあるので数学的な発想はほかの人より若干得意かと。 プログラミング言語の知識については、Scratchは結構長い間やってました*3。小5~6くらいかな?のころに少しPyth…
以前に書いたように，卒論の指導教官は杉原厚吉先生になっていただきました．杉原先生の著作はどれも非常に読みやすく，作文に関する本も出されています．その根底にあるのはシンプルさにあって，レトリックに頼ったり，あえて凝った書き方をしたりということを配していることにあります．これは言うは易く行うは難しで，例えばこのブログのようにだらだらと頭に浮かんだものを書いていると冗長になってしまいます．ここから不要な表現は省く推敲を重ねないとなかなか杉原先生の書かれるような文章にはなりません． もう一つは読者の目を引くために何かかっこいいことを書いてやろうというスケベ心が働いて余計な言葉を足したくなることを抑える…
先日、下記の記事でナップサック問題の DP を愚直に眺めました。 rsk0315.hatenablog.com 今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。 「○○（何らかの集合）の最大値」のように計算せず、○○の部分について考えていきます。 もちろん DP をする際に○○をそのまま持つと空間計算量がめちゃくちゃになる（ことに伴って時間計算量もめちゃくちゃになる）のですが、典型 DP で暗に構築されている集合を考えておくことで、そうした構造を持つ DP を考える際に理解がスムーズになる気がします。 「何々を全パターン考慮したい」となったときに「こういう漸化式を考えればよ…
gihyo.jp
language-and-engineering.hatenablog.jp
hossy.net
www.nakanihon.co.jp
www.amazon.co.jp
codeiq.hatenablog.com
www.amazon.co.jp
you-got.hatenadiary.org
ja.wikipedia.org