### vlecomte's blog

By vlecomte, history, 6 months ago, ,

Hi,

I've updated my geometry book over at https://vlecomte.github.io/cp-geo.pdf. I hope you like the new content, and I would really appreciate any feedback: suggestions, comments, typos you found, etc. :)

• Finished the chapter on "basics" and made some changes based on your feedback from last time.
• Added a whole chapter on precision issues and how to deal with them. I think some of the problems and ideas in this chapter are not obvious to all and I think they can be useful for people who don't feel very confident in geometry.

The codes are mostly untested for now so take them with a grain of salt (and tell me about the mistakes you find).

In a few weeks, I will hold a Gym contest showcasing geometry techniques/concepts that are not very common at the moment but could help make interesting problems and add some variation to geometry in ICPC-style or online contests.

There will be 5 problems for 3-4 hours. They will be hard but (I hope) interesting. After the contest, along with the editorial, my book will be updated to include all the topics that are linked to the contest. I will post an announcement as soon as the time is fixed. I hope many of you will participate. :)

UPD: I added a chapter on 3D geometry. As usual, feedback of any kind is very appreciated. It's probably full of errors. :)

•
• +450
•

 » 6 months ago, # |   0 "select to reveal" not working for me in Chromium using the default PDF Viewer plugin. It works when opened with Evince.
•  » » 6 months ago, # ^ |   +5 That was only a temporary solution (it's not ideal when printed ^^). It should be better now thanks to hyperref magic. Thanks for the feedback! :)
 » 6 months ago, # |   +3 Projective geometry would help :)
•  » » 6 months ago, # ^ |   +11 I don't know much about it but I'm intrigued. Do you have an example of how it can be useful for CP, or a problem in which it's used?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +5 645G - Armistice Area Apportionment (authored by me) is one where the right projective transformation gives a clean solution :)(And by the way, this project looks awesome! Computational geometry from a competitive programming perspective is indeed a topic that could do well with such an exposition.)
•  » » » 6 months ago, # ^ |   +5 Mainly duality and voronoi.
 » 5 months ago, # |   0 Congrats for your work! Do we need some basic knowledges to start?
•  » » 5 months ago, # ^ |   +1 In terms of geometry, not much. But I'm working with the basic assumption that readers have a good command of high school math. In the future, I might include an appendix chapter with some specific prerequisites if there is enough request.
•  » » » 4 months ago, # ^ |   0 I am in Middle School...So I don't know High School Math ( But I am Learning it) , What does Knowledge I need to read the book ?
•  » » » » 4 months ago, # ^ |   +9 I think I would advise you to just try and read the book a little and see if you get stuck on things. I think your math level should be enough to understand the biggest part of the content.Actually I would be really interested in knowing which parts prove the trickiest for a math novice. So if you do read it, it would be really nice if you could make a list of the things you didn't understand and send it to me, so that I can see if I can solve those problems. :)
 » 4 months ago, # |   +11 Auto comment: topic has been updated by vlecomte (previous revision, new revision, compare).
 » 4 months ago, # | ← Rev. 2 →   0 The issues you have with relative error on pages 9 and 10 make no sense."Relative error e=10^{-6}" essentially means that the six most significant decimal digits of the answer have to be correct. Or, if you prefer, the leftmost 20 bits. This is almost always what you want when doing floating-point calculations, simply because you cannot ask for anything less than this. If you cannot even guarantee this, the algorithm you are using is so imprecise that it's essentially useless.Formally, if the reference answer is x, all values between x*(1-e) and x*(1+e) will be considered close enough.The only situation when relative error may misbehave (i.e., when the formula above doesn't do what we want semantically) is when the result itself is close to zero. Here you can encounter some pathological cases such as the exact answer being zero, the reference solution computing 1e-15 and another solution computing -1e-15. To cover these cases, we add the clause about absolute error, essentially saying that "if the reference value is close to zero, you have to be close to zero as well".Formally, we also allow answers between x-e and x+e. This interval is usually much smaller than the previous one, and only matters when abs(x) is less than 1.Your suggestion to only set tolerance in terms of absolute error is actually just a poor man's way of properly using the relative error. The best you can do is to set it according to the largest possible instance, and in that case it will do the same thing as the currently used test for instances of that size, and it will be too loose for all small instances.Imagine a problem in which the input are some grid points with integer coordinates up to 10k. (You need such inputs, and possibly even larger ones, e.g. if you want to have a convex polygon with many vertices.) If you set a reasonable absolute precision according to the largest possible test case, then it's almost certain that some valid small test cases won't be judged correctly, allowing blatantly incorrect answers to pass.