A polygon is simple if it is a closed chain of straight line segments that do not self-intersect. Given a finite set P of input points in the Euclidean plane, the search for a simple polygon with vertex set P is a very well-known and studied computational problem, referred to as the simple polygonization. Its optimization version, that requires to find a simple polygon having either minimum or maximum area, is known to be NP-hard. Moreover, no bounded approximation algorithm is known for the minimization flavor, while the maximization one admits an algorithm guaranteeing [Formula presented] worst-case approximation ratio. In this work, we design a new algorithm to practically attack both the optimization problems, based on the genetic paradigm. We demonstrate its effectiveness through an extensive experimental evaluation that employs a reference test-bed set of input instances.

On the effectiveness of the genetic paradigm for polygonization

Cicerone S.;D'Emidio M.;Di Stefano G.;
2021

Abstract

A polygon is simple if it is a closed chain of straight line segments that do not self-intersect. Given a finite set P of input points in the Euclidean plane, the search for a simple polygon with vertex set P is a very well-known and studied computational problem, referred to as the simple polygonization. Its optimization version, that requires to find a simple polygon having either minimum or maximum area, is known to be NP-hard. Moreover, no bounded approximation algorithm is known for the minimization flavor, while the maximization one admits an algorithm guaranteeing [Formula presented] worst-case approximation ratio. In this work, we design a new algorithm to practically attack both the optimization problems, based on the genetic paradigm. We demonstrate its effectiveness through an extensive experimental evaluation that employs a reference test-bed set of input instances.
File in questo prodotto:
File Dimensione Formato  
2021_IPL.pdf

solo utenti autorizzati

Tipologia: Documento in Versione Editoriale
Licenza: Dominio pubblico
Dimensione 569.07 kB
Formato Adobe PDF
569.07 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/166534
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact