Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Enumerating Empty and Surrounding Polygons Menghitung Poligon Kosong dan Sekitarnya

Shunta TERUI, Katsuhisa YAMANAKA, Takashi HIRAYAMA, Takashi HORIYAMA, Kazuhiro KURITA, Takeaki UNO

  • pandangan teks lengkap

    1

  • Petikan Ini

Ringkasan:

Kami diberi satu set S of n titik dalam satah Euclidean. Kami menganggap bahawa S berada dalam kedudukan umum. Poligon mudah P merupakan poligon kosong of S jika setiap bucu daripada P adalah titik masuk S dan setiap titik masuk S sama ada di luar P atau puncak daripada P. Dalam kertas ini, kami mempertimbangkan masalah menghitung semua poligon kosong bagi set titik tertentu. Untuk mereka bentuk algoritma penghitungan yang cekap, kami menggunakan carian terbalik oleh Avis dan Fukuda dengan senarai anak. Kami mencadangkan algoritma yang menyenaraikan semua poligon kosong bagi S in O(n2|ε(S)|)-masa, di mana ε(S) ialah set poligon kosong bagi S. Selain itu, dengan menggunakan idea yang sama kepada masalah menghitung poligon sekeliling set titik tertentu S, kami mencadangkan algoritma penghitungan yang menyenaraikannya O(n2)-delay, manakala algoritma yang diketahui menghitung dalam O(n2 log n)-kelewatan, di mana a poligon sekeliling of S ialah poligon supaya setiap bucu poligon ialah titik masuk S dan setiap titik masuk S sama ada di dalam poligon atau bucu poligon.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1082-1091
Tarikh penerbitan
2023/09/01
Diumumkan
2023/04/03
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.2022DMP0007
Jenis Manuskrip
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
kategori
Algoritma dan Struktur Data

Pengarang

Shunta TERUI
  Iwate University
Katsuhisa YAMANAKA
  Iwate University
Takashi HIRAYAMA
  Iwate University
Takashi HORIYAMA
  Hokkaido University
Kazuhiro KURITA
  Nagoya University
Takeaki UNO
  National Institute of Informatics

Kata kunci

Contents [show]