-
Fast Polygon Triangulation
Table Of Contents Introduction Preliminaries Degeneracy Strict Total Order Monotone Polygon Montone Polygon Triangulation Example Polygon Triangulation Boundary Vertex Classification Sweepline Events Example Implementation Introduction 안녕하세요, Aeren입니다! Polygon triangulation은 classical한 computational geometry problem중 하나로, 어떤 simple polygon의 boundary가 counterclockwise하게 주어질 때, triangulation을 찾는 문제입니다. 이번 글에서 소개할 내용은 $N$을 polygon의 vertex 갯수라고 할 때 $O(N \log N)$시간 안에 위 문제를 해결하는 알고리즘입니다. 참고로 이 문제는 $O(N)$시간 안에 해결 가능함이 알려져 있습니다. (참조) Preliminaries Degeneracy 이...
-
Fully Dynamic Min Cut
Fully Dynamic Min Cut 그래프의 Minimum Cut (최소 컷) 은 그래프가 연결되지 않도록 지워야 하는 간선의 최소 개수를 뜻한다. 간선에 양의 정수 가중치가 붙으면 이를 Weighted Minimum Cut 이라고 부르고, 이 때는 그래프가 연결되지 않도록 지워야 하는 간선 가중치 합의 최소를 구해야 한다. 최소 컷을 다른 말로 Edge Connectivity 라고 부르기도 한다. 연결된 (Connected) 그래프는 최소 컷이 1 이상인 그래프와 동치이고, 이중 연결 (Biconnected) 된 그래프는 최소 컷이 2 이상인 그래프와 동치이고, 삼중 연결 (Triconnected)...
-
Object Detection
Object Detection Computer Vision(컴퓨터 비전)이란 컴퓨터 공학의 관점에서, 인간의 시각 시스템이 할 수 있는 작업을 구현하고 이를 자동화하는 방법을 다루는 학문입니다. 이를 위해 이미지 및 비디오에 대한 수집, 처리, 분석을 진행하기 위해 필요한 여러가지 주제들에 대한 연구가 이루어지고 있습니다. Object Detection(객체 감지)란 컴퓨터 비전의 하위 분야 중 하나로 전체 디지털 이미지 및 비디오 내에서 유의미한 특정 객체를 감지하는 작업을 합니다. 이러한 object detection은 Image retrieval(이미지 검색), Image annotation(이미지 주석), Face detection(얼굴 인식), Video Tracking(비디오 추적)...
-
Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures
1. Introduction 저번 글에서는 MPC를 이용한 Zero-Knowledge Proof에 대해 다루었습니다. 쉽게 요약을 해보자면 MPC-in-the-head를 이용해 증명자는 SHA256(x) = y를 만족하는 y를 알고 있다는 사실을 x를 공개하지 않고 검증자에게 납득시킬 수 있습니다. 더 나아가 원래의 증명은 검증자의 질의에 대해 증명자가 대답하는 방식으로 진행되나 Fiat-Shamir Transform을 사용하면 Non-Interactive로 증명을 만들 수 있습니다. 이렇게 Ishai et al.이 MPC-in-the-head를 제안한 후 Giacomelli et al.은 실제로 MPC를 수행하는 ZKBoo 프로토콜을 만들어냈습니다. 한편, Zero-Knowledge Proof로부터 전자서명을 만들 수 있습니다. 이건 사실...
-
대회/코딩 테스트용 간이 테스터 만들기
개요 프로그래밍 문제를 풀다 보면 종종 맞왜틀 (맞았는데 왜 틀려요)의 벽에 부딪히게 됩니다. 예제도 다 맞고, 열심히 생각해서 넣어본 여러 케이스들도 맞는데도 제출만 하면 틀렸다고 하고… 도무지 반례가 안 보일 때의 답답함은 말로 표현할 수가 없습니다. 연습용으로 문제를 풀 때에는 그나마 Polygon과 같은 전문 도구를 사용해서 스트레스를 돌리거나 견고하게 짜여진 테스트용 도구를 로컬에서 실행해보면서 반례를 찾을 수도 있습니다. Polygon의 사용법은 Acka1357 님의 글 문제 출제를 위한 플랫폼 - Polygon 사용하기에서 자세하게 확인할 수 있습니다. 하지만...